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
2
3def longest_valid_string(s: str) -> str:
4 loc = ""
5 ans = ""
6 for c, g in groupby(s):
7 glen = len(list(g))
8 ans = max([ans, loc + c * min(glen, 2)], key=len)
9 if glen > 2:
10 loc = c * 2
11 else:
12 loc += c * glen
13 return ans
14
15if __name__ == "__main__":
16 s = input()
17 res = longest_valid_string(s)
18 print(res)
191import java.util.Scanner;
2
3class Solution {
4 public static String longestValidString(String s) {
5 int sSize = s.length();
6 int startML = 0;
7 int maxLength = 0;
8
9 int start = 0;
10 int count = 1;
11 for (int i = 1; i < sSize; ++i) {
12 if (s.charAt(i) == s.charAt(i - 1)) {
13 count++;
14 } else {
15 count = 1;
16 }
17 if (count <= 2) {
18 if (i - start + 1 > maxLength) {
19 maxLength = i - start + 1;
20 startML = start;
21 }
22 } else {
23 start = i - 1;
24 count = 2;
25 }
26 }
27 return s.substring(startML, maxLength);
28 }
29
30 public static void main(String[] args) {
31 Scanner scanner = new Scanner(System.in);
32 String s = scanner.nextLine();
33 scanner.close();
34 String res = longestValidString(s);
35 System.out.println(res);
36 }
37}
381"use strict";
2
3function longestValidString(s) {
4 const sSize = s.length;
5 let startML = 0;
6 let maxLength = 0;
7
8 let start = 0;
9 let count = 1;
10
11 for (let i = 1; i < sSize; ++i) {
12 if (s.charAt(i) === s.charAt(i - 1)) {
13 count++;
14 } else {
15 count = 1;
16 }
17
18 if (count <= 2) {
19 if (i - start + 1 > maxLength) {
20 maxLength = i - start + 1;
21 startML = start;
22 }
23 } else {
24 start = i - 1;
25 count = 2;
26 }
27 }
28 return s.substr(startML, maxLength);
29}
30
31function* main() {
32 const s = yield;
33 const res = longestValidString(s);
34 console.log(res);
35}
36
37class EOFError extends Error {}
38{
39 const gen = main();
40 const next = (line) => gen.next(line).done && process.exit();
41 let buf = "";
42 next();
43 process.stdin.setEncoding("utf8");
44 process.stdin.on("data", (data) => {
45 const lines = (buf + data).split("\n");
46 buf = lines.pop();
47 lines.forEach(next);
48 });
49 process.stdin.on("end", () => {
50 buf && next(buf);
51 gen.throw(new EOFError());
52 });
53}
541function longestValidString(s: string): string {
2 const sSize = s.length;
3 let startML = 0;
4 let maxLength = 0;
5
6 let start = 0;
7 let count = 1;
8
9 for (let i = 1; i < sSize; ++i) {
10 if (s.charAt(i) === s.charAt(i - 1)) {
11 count++;
12 } else {
13 count = 1;
14 }
15
16 if (count <= 2) {
17 if (i - start + 1 > maxLength) {
18 maxLength = i - start + 1;
19 startML = start;
20 }
21 } else {
22 start = i - 1;
23 count = 2;
24 }
25 }
26 return s.substr(startML, maxLength);
27}
28
29function* main() {
30 const s = yield;
31 const res = longestValidString(s);
32 console.log(res);
33}
34
35class EOFError extends Error {}
36{
37 const gen = main();
38 const next = (line?: string) => gen.next(line ?? "").done && process.exit();
39 let buf = "";
40 next();
41 process.stdin.setEncoding("utf8");
42 process.stdin.on("data", (data) => {
43 const lines = (buf + data).split("\n");
44 buf = lines.pop() ?? "";
45 lines.forEach(next);
46 });
47 process.stdin.on("end", () => {
48 buf && next(buf);
49 gen.throw(new EOFError());
50 });
51}
52