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 str 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()))
14
1import 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}
41
1const 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});
38

Still not clear? Submit the part you don't understand to our editors.