Microsoft OA Longest Substring Without Two Contiguous Occurrences of Letter

Microsoft Online Assessment Longest Substring Without Two Contiguous Occurrences of Letter

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.

Also See: Microsoft Online Assessment Questions and Solution

Example 1:

Input: aabbaaaaabb

Output: aabbaa

Example 2:

Input: aabbaabbaabbaaa

Output: aabbaabbaabbaa

Solution

Program Python:

from itertools import groupby
def longestValidString(str) -> str:

      loc, ans = '', ''
      for c, g in groupby(str):
          glen = len(list(g))
          ans = max([ans, loc + c * min(glen, 2)], key=len)
          if glen > 2:
              loc = c*2
          else:
              loc += c*glen
      return ans
if __name__ == '__main__':
    print(longestValidString(input()))

Program Java:

import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;
class Solution {
    public static String longestValidString(String str) {

        int s_size = str.length();
        int start_ml = 0;
        int max_length = 0;
        int start = 0;
        int count = 1;
        for (int i = 1; i < s_size; ++i) {
            if (str.charAt(i) == str.charAt(i - 1)) {
                count++;
            } else {
                count = 1;
            }
            if (count <= 2) {
                if (i - start + 1 > max_length) {
                    max_length = i - start + 1;
                    start_ml = start;
                }
            } else {
                start = i - 1;
                count = 2;
            }
        }
        return str.substring(start_ml, max_length);
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        scanner.close();
        System.out.println(longestValidString(str));
    }
}

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA 2021 (Online Assessment) Questions Preparation

Microsoft Online Assessment 2021 Questions

Leave a Comment