Microsoft Online Assessment (OA) - 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 it does not contain more than two contiguous occurrences of a and b.
Example 1:
Input: aabbaaaaabb
Output: aabbaa
Example 2:
Input: aabbaabbaabbaaa
Output: aabbaabbaabbaa
Try it yourself
Implementation
1from itertools import groupby
2def longestValidString(str) -> str:
3 loc, ans = '', ''
4 for c, g in groupby(str):
5 glen = len(list(g))
6 ans = max([ans, loc + c * min(glen, 2)], key=len)
7 if glen > 2:
8 loc = c*2
9 else:
10 loc += c*glen
11 return ans
12if __name__ == '__main__':
13 print(longestValidString(input()))
141import java.util.Scanner;
2import java.util.HashSet;
3import java.util.Set;
4
5class Solution {
6
7 public static String longestValidString(String str) {
8 int s_size = str.length();
9 int start_ml = 0;
10 int max_length = 0;
11
12 int start = 0;
13 int count = 1;
14 for (int i = 1; i < s_size; ++i) {
15 if (str.charAt(i) == str.charAt(i - 1)) {
16 count++;
17 } else {
18 count = 1;
19 }
20 if (count <= 2) {
21 if (i - start + 1 > max_length) {
22 max_length = i - start + 1;
23 start_ml = start;
24 }
25 } else {
26 start = i - 1;
27 count = 2;
28 }
29 }
30 return str.substring(start_ml, max_length);
31 }
32
33 public static void main(String[] args) {
34 Scanner scanner = new Scanner(System.in);
35 String str = scanner.nextLine();
36 scanner.close();
37 System.out.println(longestValidString(str));
38 }
39
40}
411const readline = require('readline');
2
3function longestValidString(str) {
4 let s_size = str.length;
5 let start_ml = 0;
6 let max_length = 0;
7
8 let start = 0;
9 let count = 1;
10
11 for (let i = 1; i < s_size; ++i) {
12
13 if (str.charAt(i) === str.charAt(i - 1)) {
14 count++;
15 } else {
16 count = 1;
17 }
18
19 if (count <= 2) {
20 if (i - start + 1 > max_length) {
21 max_length = i - start + 1;
22 start_ml = start;
23 }
24 } else {
25 start = i - 1;
26 count = 2;
27 }
28 }
29
30 return str.substr(start_ml, max_length);
31}
32
33const rl = readline.createInterface(process.stdin);
34rl.on('line', (input) => {
35 rl.close();
36 console.log(longestValidString(input));
37});
38Got 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.