Contest 2 Solutions

# ​​No As

In this problem, we need to return the length of the longest substring that doesn’t contain any of the character “a”. The bounds are small enough to allow a variety of approaches.

One approach is to loop through the string and keep a counter of the most consecutive characters that we have seen that are not ‘a’s. If we see an ‘a’, we can set this count to zero, otherwise, we can increment this count. The answer is the maximum value of the counter throughout our loop.

This can be implemented with the following code:
​​s = raw_input()
​​
​​ans = 0
​​cur = 0
​​
​​for x in s:
​​  if x == 'a':
​​    cur = 0
​​  else:
​​    cur += 1
​​  ans = max(ans, cur)
​​
​​print ans

For an alternate solution, we can use the split  function on python to split the strings by “a”s. Then, we can iterate through the array generated from split and take the one with maximum length. This can be done in one line in python
​​"bacadc".split() -> ["b", "c", "dc"]

​​print max(map(len, raw_input().split("a")))

# ​​After A

We can loop through the string and add all characters that immediately appear after an ’a’ to a set. Then, we print the size of the set.

​​s = raw_input()
​​
​​ans = set()
​​for i in range(1,len(s)):
​​  if s[i-1] == 'a':
​​    ans.add(s[i])
​​
​​print len(ans)

Sample implementation:
​​s = raw_input()
​​print len(set(y for x,y in zip(s, s[1:]) if x == 'a'))

Alternatively, we can see if “aa”, “ab”, “ac”, …, “az” appears in s. The number of different strings that appear in s is the answer.

Another implementation
​​s = raw_input()
​​print sum("a"+chr(ord('a')+i) in s for i in range(26))

# ​​Maximum Range

An optimal solution is to take all ‘+’ characters or all ‘-’ characters

We’ll show we can’t do any better. Suppose there is a better solution that had a combination of both ‘+’ and ‘-’ characters. Suppose we simulate these instructions until we hit the minimum overall value. Now, our range is limited by the number of ‘+’ characters total (analogously, if we simulate these instructions until we hit the maximum overall value, the range is limited by the number of ‘-’ characters). This shows that this solution can’t be strictly better.