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

Overview

Basic Data Structures

Basic Algorithms

Warm Up

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Introduction

DFS on Tree

Binary Search Tree

Combinatorial Search

Memoization

Pruning

Dedup

Additional Practices

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Sequence

Grid

Dynamic number of subproblems

Partition

Interval

Two Sequences

Game Theory

0-1 Knapsack

Bitmask

Tree

Introduction

Generalized

Binary Search

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Greedy

Monotonic Stack

Line Sweep

Interval

Tree Traversal without Recursion

Composite Patterns

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Microsoft Online Assessment (OA) - Longest Substring Without Two Contiguous Occurrences of Letter

Example 1:

Input: aabbaaaaabb

Output: aabbaa

Example 2:

Input: aabbaabbaabbaaa

Output: aabbaabbaabbaa

Try it yourself

Implementation

Input: `aabbaaaaabb`

Output: `aabbaa`

Input: `aabbaabbaabbaaa`

Output: `aabbaabbaabbaa`