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
1import java.util.Scanner;
2
3class Solution {
4 public static int semiSubstring(String s) {
5 int MAX_COUNT = 3;
6 if (s.length() < MAX_COUNT) {
7 return s.length();
8 }
9
10 int count = 1, result = 1;
11 for (int i = 1; i < s.length() - 1; i++) {
12 if (s.charAt(i - 1) == s.charAt(i) && s.charAt(i + 1) == s.charAt(i)) {
13 result = Math.max(result, count + 1);
14 count = 1;
15 } else {
16 count++;
17 }
18 }
19
20 return Math.max(result, count + 1);
21 }
22
23 public static void main(String[] args) {
24 Scanner scanner = new Scanner(System.in);
25 String s = scanner.nextLine();
26 scanner.close();
27 int res = semiSubstring(s);
28 System.out.println(res);
29 }
30}
31
1function semiSubstring(s) {
2 const MAX_COUNT = 3;
3 if (s.length < MAX_COUNT)
4 return s.length;
5 let count = 1, result = 1;
6 for (let i = 1; i < s.length - 1; i++) {
7 if (s.charAt(i-1) === s.charAt(i) && s.charAt(i + 1) === s.charAt(i)) {
8 result = Math.max(result, count + 1);
9 count = 1;
10 } else {
11 count++;
12 }
13 }
14 return Math.max(result, count + 1);
15}
16
17function* main() {
18 const s = yield;
19 const res = semiSubstring(s);
20 console.log(res);
21}
22
23class EOFError extends Error {}
24{
25 const gen = main();
26 const next = (line) => gen.next(line).done && process.exit();
27 let buf = '';
28 next();
29 process.stdin.setEncoding('utf8');
30 process.stdin.on('data', (data) => {
31 const lines = (buf + data).split('\n');
32 buf = lines.pop();
33 lines.forEach(next);
34 });
35 process.stdin.on('end', () => {
36 buf && next(buf);
37 gen.throw(new EOFError());
38 });
39}
40
Still not clear? Submit the part you don't understand to our editors.