**Longest Semi-Alternating Substring Solution**

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.

**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:***Longest Semi-Alternating Substring Solution** in 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:**Longest Semi-Alternating Substring Solution** in 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) {
// write your code here
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:***Longest Semi-Alternating Substring Solution** in 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;
cout << solution("eedaaad") << endl;
cout << solution("xxxtxxx") << endl;
cout << solution("uuuuxaaaaxuuu") << endl;
return 0;
}
```

**Microsoft Online Assessment 2023 Questions List**

*Maximal Network Rank Solution**Min Deletions To Obtain String in Right Format**Day of week that is K days later Solution**Minimum Adjacent Swaps to Make Palindrome Solution**Lexicographically Smallest String**Longest Substring Without Two Contiguous Occurrences of Letter**String Without 3 Identical Consecutive Letters**Microsoft OA Longest Semi-Alternating Substring**Microsoft OA Min Steps to Make Piles Equal Height**Max Inserts to Obtain String Without 3 Consecutive ‘a’**Concatenated String Length with unique Characters**Largest K such that both K and -K exist in array**Microsoft OA Min Adj Swaps to Group Red Balls**Maximum Length of a Concatenated String with Unique Characters**Microsoft OA Unique Integers That Sum Up To 0**Find N Unique Integers Sum up to Zero**Microsoft OA Particle Velocity Solution**Microsoft OA Arithmetic Slices Solution**Microsoft OA Widest Path Without Trees Solution**Microsoft OA Jump Game Solution**Microsoft OA Fair Indexes Solution*