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)
141import 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}
311"use strict";
2
3function semiSubstring(s) {
4 const MAX_COUNT = 3;
5 if (s.length < MAX_COUNT) {
6 return s.length;
7 }
8 let count = 1;
9 let result = 1;
10 for (let i = 1; i < s.length - 1; i++) {
11 if (s.charAt(i - 1) === s.charAt(i) && s.charAt(i + 1) === s.charAt(i)) {
12 result = Math.max(result, count + 1);
13 count = 1;
14 } else {
15 count++;
16 }
17 }
18 return Math.max(result, count + 1);
19}
20
21function* main() {
22 const s = yield;
23 const res = semiSubstring(s);
24 console.log(res);
25}
26
27class EOFError extends Error {}
28{
29 const gen = main();
30 const next = (line) => gen.next(line).done && process.exit();
31 let buf = "";
32 next();
33 process.stdin.setEncoding("utf8");
34 process.stdin.on("data", (data) => {
35 const lines = (buf + data).split("\n");
36 buf = lines.pop();
37 lines.forEach(next);
38 });
39 process.stdin.on("end", () => {
40 buf && next(buf);
41 gen.throw(new EOFError());
42 });
43}
44