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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫