Microsoft Online Assessment (OA) - Longest Substring Without Two Contiguous Occurrences of Letter

Given a string str containing only a and b, find the longest substring of str such that str does not contain more than two contiguous occurrences of a and b.

Example 1:

Input: aabbaaaaabb

Output: aabbaa

Example 2:

Input: aabbaabbaabbaaa

Output: aabbaabbaabbaa

Try it yourself

Implementation

1
+
from itertools import groupby
1
2
def longestValidString(str) -> str:
2
-
      # WRITE YOUR BRILLIANT CODE HERE
3
+
      loc, ans = '', ''
4
+
      for c, g in groupby(str):
5
+
          glen = len(list(g))
6
+
          ans = max([ans, loc + c * min(glen, 2)], key=len)
7
+
          if glen > 2:
8
+
              loc = c*2
9
+
          else:
10
+
              loc += c*glen
11
+
      return ans
3
12
if __name__ == '__main__':
4
13
    print(longestValidString(input()))