# Microsoft OA Longest Substring Without Two Contiguous Occurrences of Letter

Page Contents

Microsoft Online Assessment Longest Substring Without Two Contiguous Occurrences of Letter

## Longest Substring Without Two Contiguous Occurrences of Letter

Given a string `str` containing only `a` and `b`, find the longest substring of `str` such that `str` does not contain more than two contiguous occurrences of `a` and `b`.

Also See: Microsoft Online Assessment Questions and Solution

Example 1:

Input: `aabbaaaaabb`

Output: `aabbaa`

Example 2:

Input: `aabbaabbaabbaaa`

Output: `aabbaabbaabbaa`

## Solution

Program Python:

``````from itertools import groupby
def longestValidString(str) -> str:

loc, ans = '', ''
for c, g in groupby(str):
glen = len(list(g))
ans = max([ans, loc + c * min(glen, 2)], key=len)
if glen > 2:
loc = c*2
else:
loc += c*glen
return ans
if __name__ == '__main__':
print(longestValidString(input()))
``````

Program Java:

``````import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;
class Solution {
public static String longestValidString(String str) {

int s_size = str.length();
int start_ml = 0;
int max_length = 0;
int start = 0;
int count = 1;
for (int i = 1; i < s_size; ++i) {
if (str.charAt(i) == str.charAt(i - 1)) {
count++;
} else {
count = 1;
}
if (count <= 2) {
if (i - start + 1 > max_length) {
max_length = i - start + 1;
start_ml = start;
}
} else {
start = i - 1;
count = 2;
}
}
return str.substring(start_ml, max_length);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
scanner.close();
System.out.println(longestValidString(str));
}
}``````

Also See: AMCAT Study Materials, Preparation Guide

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

Microsoft Online Assessment 2021 Questions