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 if (s.isEmpty()) return "";
6
7 String loc = "";
8 String ans = "";
9
10 int i = 0;
11 while (i < s.length()) {
12 char c = s.charAt(i);
13 int count = 0;
14
15 while (i < s.length() && s.charAt(i) == c) {
16 count++;
17 i++;
18 }
19
20 int take = Math.min(count, 2);
21 String candidate = loc + repeat(c, take);
22
23 if (candidate.length() > ans.length()) {
24 ans = candidate;
25 }
26
27 if (count > 2) {
28 loc = repeat(c, 2);
29 } else {
30 loc = candidate;
31 }
32 }
33
34 return ans;
35 }
36
37 private static String repeat(char c, int count) {
38 StringBuilder sb = new StringBuilder();
39 for (int i = 0; i < count; i++) {
40 sb.append(c);
41 }
42 return sb.toString();
43 }
44
45 public static void main(String[] args) {
46 Scanner scanner = new Scanner(System.in);
47 String s = scanner.nextLine();
48 scanner.close();
49 String res = longestValidString(s);
50 System.out.println(res);
51 }
52}
531"use strict";
2
3function longestValidString(s) {
4 if (s.length === 0) return "";
5
6 let loc = "";
7 let ans = "";
8
9 let i = 0;
10 while (i < s.length) {
11 let c = s[i];
12 let count = 0;
13
14 while (i < s.length && s[i] === c) {
15 count++;
16 i++;
17 }
18
19 let take = Math.min(count, 2);
20 let candidate = loc + c.repeat(take);
21
22 if (candidate.length > ans.length) {
23 ans = candidate;
24 }
25
26 if (count > 2) {
27 loc = c.repeat(2);
28 } else {
29 loc = candidate;
30 }
31 }
32
33 return ans;
34}
35
36function* main() {
37 const s = yield;
38 const res = longestValidString(s);
39 console.log(res);
40}
41
42class EOFError extends Error {}
43{
44 const gen = main();
45 const next = (line) => gen.next(line).done && process.exit();
46 let buf = "";
47 next();
48 process.stdin.setEncoding("utf8");
49 process.stdin.on("data", (data) => {
50 const lines = (buf + data).split("\n");
51 buf = lines.pop();
52 lines.forEach(next);
53 });
54 process.stdin.on("end", () => {
55 buf && next(buf);
56 gen.throw(new EOFError());
57 });
58}
591function longestValidString(s: string): string {
2 if (s.length === 0) return "";
3
4 let loc = "";
5 let ans = "";
6
7 let i = 0;
8 while (i < s.length) {
9 let c = s[i];
10 let count = 0;
11
12 while (i < s.length && s[i] === c) {
13 count++;
14 i++;
15 }
16
17 let take = Math.min(count, 2);
18 let candidate = loc + c.repeat(take);
19
20 if (candidate.length > ans.length) {
21 ans = candidate;
22 }
23
24 if (count > 2) {
25 loc = c.repeat(2);
26 } else {
27 loc = candidate;
28 }
29 }
30
31 return ans;
32}
33
34function* main() {
35 const s = yield;
36 const res = longestValidString(s);
37 console.log(res);
38}
39
40class EOFError extends Error {}
41{
42 const gen = main();
43 const next = (line?: string) => gen.next(line ?? "").done && process.exit();
44 let buf = "";
45 next();
46 process.stdin.setEncoding("utf8");
47 process.stdin.on("data", (data) => {
48 const lines = (buf + data).split("\n");
49 buf = lines.pop() ?? "";
50 lines.forEach(next);
51 });
52 process.stdin.on("end", () => {
53 buf && next(buf);
54 gen.throw(new EOFError());
55 });
56}
57