Microsoft Online Assessment (OA) - Longest Semi-Alternating Substring
Given a string S containing only characters a and b. A substring (contiguous fragment) of S
is called a semi-alternating substring if it does not contain three identical consecutive characters.
In other words, it does not contain either 'aaa' or 'bbb' substrings. Note that the whole S is its own substring.
Example 1:
Input: baaabbabbb
Output: 7
Explanation:
the longest semi-alternating substring is aabbabb
Example 2:
Input: babba
Output: 5
Explanation:
Whole S is semi-alternating.
Example 3:
Input: abaaaa
Output: 4
Explanation:
The first four letters of S create a semi-alternating substring.
Try it yourself
Implementation
1def semi_substring(s: str) -> int:
2 max_len = 0
3 left = 0
4 for right in range(len(s)):
5 if right - left + 1 >= 3 and s[right] == s[right - 1] == s[right - 2]:
6 left = right - 1
7 max_len = max(max_len, right - left + 1)
8 return max_len
9
10if __name__ == '__main__':
11 s = input()
12 res = semi_substring(s)
13 print(res)
14