Microsoft OA Longest Semi-Alternating Substring

Microsoft Online Assessment Question, Longest Semi-Alternating Substring

Longest Semi-Alternating Substring

Given a string S containing only characters a and b. A substring (contiguous fragment) of S is called a semi-alternating substring if it does not contain three identical consecutive characters. In other words, it does not contain either ‘aaa’ or ‘bbb’ substrings. Note that the whole S is its own substring.

Also See: Microsoft Online Assessment Questions and Solution

Example 1:
Input: baaabbabbb
Output: 7
Explanation:
the longest semi-alternating substring is aabbabb

Example 2:
Input: babba
Output: 5
Explanation:
Whole S is semi-alternating.

Example 3:
Input: abaaaa
Output: 4
Explanation:
The first four letters of S create a semi-alternating substring.

Solution

Program Python:

def semi_substring(s: str) -> int:
    max_len = 0
    left = 0
    for right in range(len(s)):
        if right - left + 1 >= 3 and s[right] == s[right - 1] == s[right - 2]:
            left = right - 1
        max_len = max(max_len, right - left + 1)
    return max_len
if __name__ == '__main__':
    s = input()
    res = semi_substring(s)
    print(res)

Program Java:

import java.util.Scanner;
class Solution {
    public static int semiSubstring(String s) {
        int MAX_COUNT = 3;
        if (s.length() < MAX_COUNT) {
            return s.length();
        }
        int count = 1, result = 1;
        for (int i = 1; i < s.length() - 1; i++) {
            if (s.charAt(i - 1) == s.charAt(i) && s.charAt(i + 1) == s.charAt(i)) {
                result = Math.max(result, count + 1);
                count = 1;
            } else {
                count++;
            }
        }
        return Math.max(result, count + 1);
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        scanner.close();
        int res = semiSubstring(s);
        System.out.println(res);
    }
}

Program Javascript:

function semiSubstring(s) {
    const MAX_COUNT = 3;
    if (s.length < MAX_COUNT)
        return s.length;
    let count = 1, result = 1;
    for (let i = 1; i < s.length - 1; i++) {
        if (s.charAt(i-1) === s.charAt(i) && s.charAt(i + 1) === s.charAt(i)) {
            result = Math.max(result, count + 1);
            count = 1;
        } else {
            count++;
        }
    }
    return Math.max(result, count + 1);
}
function* main() {
    const s = yield;
    const res = semiSubstring(s);
    console.log(res);
}
class EOFError extends Error {}
{
    const gen = main();
    const next = (line) => gen.next(line).done && process.exit();
    let buf = '';
    next();
    process.stdin.setEncoding('utf8');
    process.stdin.on('data', (data) => {
        const lines = (buf + data).split('\n');
        buf = lines.pop();
        lines.forEach(next);
    });
    process.stdin.on('end', () => {
        buf && next(buf);
        gen.throw(new EOFError());
    });
}

Also See: AMCAT Study Materials, Preparation Guide

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

Microsoft Online Assessment 2021 Questions

Leave a Comment