# Longest Semi-Alternating Substring Microsoft OA

Page Contents

Microsoft Online Assessment Question, Longest Semi-Alternating Substring

## Longest Semi-Alternating Substring

You are given a string SS of length NN containing only characters `a` and `b`. A substring (contiguous fragment) of SS 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 whole SS is its own substring.

Write a function, which given a string SS, returns the length of the longest semi-alternating substring of SS.

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:

Double pointer, fix the pointer on the left, then move the pointer on the right until the condition is met, and then move the pointer on the left.

```class Solution:
def longestSemiAlternatingSubstring(self, s):
n = len(s)
if n < 3:
return n
res, cnt = 0, 1
left = 0
for right in range(n):
if right > 0 and s[right] == s[right - 1]:
cnt += 1
else:
cnt = 1
if cnt == 3:
left = right - 1
cnt = 2
res = max(res, right - left + 1)

return res ```

Program Java:

The idea is a double pointer, we use a variable to record the last character we saw c c c , then use a variable x x x records the number of consecutive occurrences of the character, and also needs to record the left end point of the longest substring that satisfies the condition ending at the current position; traverse s s s , if it is found that the current character is different from the one seen last time, it means that the substring can be extended, update c c c and update x = 1 x=1 x=1 , keep the left endpoint unchanged; otherwise, it means that the same character is seen, update x x x is x + 1 x+1 x+1 , look at x ≥ 3 x\ge 3 x≥3 is it true, if it is true, it means that you have seen three consecutive identical characters, move the left pointer to the current position minus 1 1 1 , otherwise it will not move; the answer will be updated every time a character is traversed. code show as below:

```import java.util.Scanner;
class Solution {
public int longestSemiAlternatingSubstring(String s) {
int res = 0, count = 0;
char ch = 0;

for (int i = 0, j = 0; i < s.length(); i++) {
if (i == 0 || s.charAt(i) != ch) {
ch = s.charAt(i);
count = 1;
} else {
count++;
if (count >= 3) {
j = i - 1;
}
}

res = Math.max(res, i - j + 1);
}

return res;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();

int res = longestSemiAlternatingSubstring(s);
System.out.println(res);
}
}```

Program C++:

This question is similar to String Without 3 Identical Consecutive Letters but here we need to find a longest substring which doesn’t contain three identical consecutive characters and return it’s length.

```#include <iostream>
#include <string>

using namespace std;

int solution(const string & s) {
const int MAX_COUNT = 3;
int s_len = s.length();
if(s_len < MAX_COUNT) { return s_len; }
int count = 1, result = 1;
// Scan whole string and count it's characters.
for(int i = 1; i < s_len - 1; ++i) {
// If we meet 3 consecutive characters
if((s[i-1] == s[i]) && (s[i+1] == s[i])) {
// save the counter as result if it is bigger than the previous result
result = max(result,count+1);
// and drop the counter to 1
count = 1;
}
else { count++; }
}
// return maximal result
return max(result,count+1);
}

int main() {
cout << solution("baaabbabbb") << " Expected: 7" << endl;
cout << solution("babba") << " Expected: 5" << endl;
cout << solution("abaaaa") << " Expected: 4" << endl;