Whenever George asks Lily to hang out, she’s busy doing homework. George wants to help her finish it faster, but he’s in over his head! Can you help George understand Lily’s homework so she can hang out with him?

Consider an array of m distinct integers, arr = [a[0], a[1], …, a[n-1]]. George can swap any two elements of the array any number of times. An array is *beautiful* if the sum of |a[i] – a[i-1] among 0 < i < n is minimal.

time complexity is O(N*log(N))

space complexity is O(N)

Let us rephrase the problem to a sorting problem: Find the number of swaps to make the array sorted. We need to consider both ascending and descending arrays. The solution assumes no duplicates.

def cntSwaps(arr): positions = sorted(list(enumerate(arr)), key=lambda e: e[1]) swaps = 0 for idx in xrange(len(arr)): while True: if (positions[idx][0] == idx): break else: swaps += 1 swapped_idx = positions[idx][0] positions[idx], positions[swapped_idx] = positions[swapped_idx], positions[idx] return swaps def lilysHomework(arr): return min(cntSwaps(arr), cntSwaps(arr[::-1]))

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

A gene is represented as a string of length N (where is divisible by 4), composed of the letters A, C, G, and T. It is considered to be *steady* if each of the four letters occurs exactly 1/4 times. For example, GACT and AAGGCCTT are both steady genes.

time complexity is O(N)

space complexity is O(1)

A bit of trivia: I’ve looked at this problem a couple times 2 years ago and I could not figure it out. Sometimes it is good to take a long break

In the first pass I establish how many occurrences there are of each character. Then I establish how many are missing to make the string steady. Remember that the number of occurrences needs to be evenly distributed.

The second pass takes advantage of the caterpillar method. I am looking for the shortest string that contains all the extra characters. They need to be replaced by the missing characters. All others can just be replaced with the same character. The caterpillar extends as long as it does not hit one of the extra characters. It shortens if it contains more extra characters than are needed.

def steadyGene(gene): min_length_string = len(gene) occurences = dict() occurences['A'] = 0 occurences['G'] = 0 occurences['C'] = 0 occurences['T'] = 0 expected = len(gene) // 4 for g in gene: occurences[g] += 1 for x in occurences: occurences[x] = max(0, occurences[x] - expected) if occurences['A'] == 0 and occurences['G'] == 0 and occurences['C'] == 0 and occurences['T'] == 0: return 0 found = dict() found['A'] = 0 found['G'] = 0 found['C'] = 0 found['T'] = 0 tail = 0 head = 0 while head != len(gene): found[gene[head]] += 1 if found['A'] >= occurences['A'] and \ found['C'] >= occurences['C'] and \ found['G'] >= occurences['G'] and \ found['T'] >= occurences['T']: # this is a valid candidate min_length_string = min(min_length_string, head-tail+1) # try to shorten it while found[gene[tail]] > occurences[gene[tail]]: found[gene[tail]] -= 1 tail += 1 min_length_string = min(min_length_string, head-tail+1) head += 1 return min_length_string

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

Sherlock considers a string to be *valid* if all characters of the string appear the same number of times. It is also *valid* if he can remove just 1 character at 1 index in the string, and the remaining characters will occur the same number of times. Given a string , determine if it is *valid*. If so, return `YES`

, otherwise return `NO`

.

time complexity is O(N)

space complexity is O(N)

This is one of the easier medium problems. Create a character occurrence map. Then create an occurrence-occurrence map. If all the occurrences are the same (size is 1) the string is valid. If there is exactly one character that occurs exactly once, it is also valid. Otherwise invalid

def isValid(S): char_map = Counter(S) char_occurence_map = Counter(char_map.values()) if len(char_occurence_map) == 1: return True if len(char_occurence_map) == 2: for v in char_occurence_map.values(): if v == 1: return True return False

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

Amanda has a string of lowercase letters that she wants to copy to a new string. She can perform the following operations with the given costs. She can perform them any number of times to construct a new string p:

- Append a character to the end of string p at a cost of 1 dollar.
- Choose any substring of p and append it to the end of at no charge.

time complexity is O(N)

space complexity is O(N)

The solution sounds too easy, but it is still very simple. A substring of length 1 is still a substring. Each character in the final string needs to be copied once for 1$. Each other occurrence of that string can be copied for 0$. Aka just count the number of distinct letters in the expected string.

def stringConstruction(s): return len(set(s))

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

A weighted string is a string of lowercase English letters where each letter has a *weight*. Character weights are 1 to 26 from a to z…

time complexity is O(N)

space complexity is O(N)

Parsing the string for every query is suboptimal, so I first preprocess the string. Now we know that uniform strings contain the same characters. A string can be of length 1. Do a single pass of the string and create all uniform substrings.

def weightedUniformStrings(s, queries): weights = set() prev = -1 length = 0 for c in s: weight = ord(c) - ord('a') + 1 weights.add(weight) if prev == c: length += 1 weights.add(length*weight) else: prev = c length = 1 rval = [] for q in queries: if q in weights: rval.append("Yes") else: rval.append("No") return rval

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

We say that a string contains the word `hackerrank`

if a subsequence of its characters spell the word `hackerrank`

. For example, if string s = haacckkerrannkk it does contain `hackerrank`

, but s = haacckkerannk does not. In the second case, the second `r`

is missing. If we reorder the first string as , it no longer contains the subsequence due to ordering.

time complexity is O(N)

space complexity is O(1)

Keep two pointers. One to the expected string (needle) and one to the input string. If you find the needle in the haystack before you run out of characters, you are good.

def hackerrankInString(s): needle = 'hackerrank' idx_in_needle = 0 for c in s: if c == needle[idx_in_needle]: idx_in_needle += 1 if idx_in_needle == len(needle): break if idx_in_needle == len(needle): return "YES" else: return "NO"

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

Sami’s spaceship crashed on Mars! She sends a series of `SOS`

messages to Earth for help.

time complexity is O(N)

space complexity is O(1)

We know that the message is basically a lot of concatenated SOS strings. There is no magic to this one.

S = raw_input().strip() errors = 0 for i in xrange(len(S)): if i % 3 == 0 and S[i] != 'S': errors += 1 if i % 3 == 1 and S[i] != 'O': errors += 1 if i % 3 == 2 and S[i] != 'S': errors += 1 print errors

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

Louise joined a social networking site to stay in touch with her friends. The signup page required her to input a *name* and a *password*. However, the password must be *strong*. The website considers a password to be *strong* if it satisfies the following criteria:

- Its length is at least 6.
- It contains at least one digit.
- It contains at least one lowercase English character.
- It contains at least one uppercase English character.
- It contains at least one special character. The special characters are:
`!@#$%^&*()-+`

She typed a random string of length n in the password field but wasn’t sure if it was strong. Given the string she typed, can you find the minimum number of characters she must add to make her password strong?

time complexity is O(N)

space complexity is O(1)

This is a pythonesque solution by Jay Mistry. The O(4*N) complexity might be suboptimal, but it showcases a nice use of the language.

def minimumNumber(n, password): count = 0 if any(i.isdigit() for i in password)==False: count+=1 if any(i.islower() for i in password)==False: count+=1 if any(i.isupper() for i in password)==False: count+=1 if any(i in '!@#$%^&*()-+' for i in password)==False: count+=1 return max(count,6-n)

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

Alice wrote a sequence of words in CamelCase as a string of letters, , having the following properties:

- It is a concatenation of one or more
*words*consisting of English letters. - All letters in the first word are
*lowercase*. - For each of the subsequent words, the first letter is
*uppercase*and rest of the letters are*lowercase*.

Given s , print the number of words in s on a new line.

For example, s = OneTwoThree . There are 3 words in the string.

time complexity is O(N)

space complexity is O(1)

Since the input always has at least 1 character, we can assume that there will always be at least one word. Each upper case later identifies the next word. So the result is number of capital letters + 1.

s = raw_input().strip() cnt = 1 for c in s: if c.isupper(): cnt += 1 print cnt

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

Steve has a string of lowercase characters in range `ascii[‘a’..’z’]`

. He wants to reduce the string to its shortest length by doing a series of operations. In each operation he selects a pair of adjacent lowercase letters that match, and he deletes them. For instance, the string `aab`

could be shortened to `b`

in one operation.

Steve’s task is to delete as many characters as possible using this method and print the resulting string. If the final string is empty, print `Empty String`

time complexity is O(N)

space complexity is O(N)

The solution creates a stack of values. If the top value on the stack is equivalent to the next value, simply remove both. This solution assumes that there are only ever 2 values next to each other. If any adjacent values were to be removed, I would require more loops.

i = raw_input() s = [] for c in i: if not s: s.append(c) else: if s[-1] == c: s.pop() else: s.append(c) if not s: print "Empty String" else: print ''.join(s)

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>