# Microsoft OA Longest Semi-Alternating Substring

Page Contents

Microsoft Online Assessment Question, Longest Semi-Alternating Substring

## 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.

Also See: Microsoft Online Assessment Questions and Solution

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.

## Solution

Program Python:

```def semi_substring(s: str) -> int:
max_len = 0
left = 0
for right in range(len(s)):
if right - left + 1 >= 3 and s[right] == s[right - 1] == s[right - 2]:
left = right - 1
max_len = max(max_len, right - left + 1)
return max_len
if __name__ == '__main__':
s = input()
res = semi_substring(s)
print(res)```

Program Java:

```import java.util.Scanner;
class Solution {
public static int semiSubstring(String s) {
int MAX_COUNT = 3;
if (s.length() < MAX_COUNT) {
return s.length();
}
int count = 1, result = 1;
for (int i = 1; i < s.length() - 1; i++) {
if (s.charAt(i - 1) == s.charAt(i) && s.charAt(i + 1) == s.charAt(i)) {
result = Math.max(result, count + 1);
count = 1;
} else {
count++;
}
}
return Math.max(result, count + 1);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
scanner.close();
int res = semiSubstring(s);
System.out.println(res);
}
}```

Program Javascript:

```function semiSubstring(s) {
const MAX_COUNT = 3;
if (s.length < MAX_COUNT)
return s.length;
let count = 1, result = 1;
for (let i = 1; i < s.length - 1; i++) {
if (s.charAt(i-1) === s.charAt(i) && s.charAt(i + 1) === s.charAt(i)) {
result = Math.max(result, count + 1);
count = 1;
} else {
count++;
}
}
return Math.max(result, count + 1);
}
function* main() {
const s = yield;
const res = semiSubstring(s);
console.log(res);
}
class EOFError extends Error {}
{
const gen = main();
const next = (line) => gen.next(line).done && process.exit();
let buf = '';
next();
process.stdin.setEncoding('utf8');
process.stdin.on('data', (data) => {
const lines = (buf + data).split('\n');
buf = lines.pop();
lines.forEach(next);
});
process.stdin.on('end', () => {
buf && next(buf);
gen.throw(new EOFError());
});
}```

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA 2021 (Online Assessment) Questions Preparation

Microsoft Online Assessment 2021 Questions