Longest Semi-Alternating Substring Microsoft OA

Microsoft Online Assessment Question, Longest Semi-Alternating Substring

Longest Semi-Alternating Substring

You are given a string SS of length NN containing only characters a and b. A substring (contiguous fragment) of SS 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 whole SS is its own substring.

Write a function, which given a string SS, returns the length of the longest semi-alternating substring of SS.

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:

Double pointer, fix the pointer on the left, then move the pointer on the right until the condition is met, and then move the pointer on the left.

class Solution:
    def longestSemiAlternatingSubstring(self, s):
        n = len(s)
        if n < 3:
            return n
        res, cnt = 0, 1
        left = 0
        for right in range(n):
            if right > 0 and s[right] == s[right - 1]:
                cnt += 1
            else:
                cnt = 1
            if cnt == 3:
                left = right - 1
                cnt = 2
            res = max(res, right - left + 1)

        return res 

Program Java:

The idea is a double pointer, we use a variable to record the last character we saw c c c , then use a variable x x x records the number of consecutive occurrences of the character, and also needs to record the left end point of the longest substring that satisfies the condition ending at the current position; traverse s s s , if it is found that the current character is different from the one seen last time, it means that the substring can be extended, update c c c and update x = 1 x=1 x=1 , keep the left endpoint unchanged; otherwise, it means that the same character is seen, update x x x is x + 1 x+1 x+1 , look at x ≥ 3 x\ge 3 x≥3 is it true, if it is true, it means that you have seen three consecutive identical characters, move the left pointer to the current position minus 1 1 1 , otherwise it will not move; the answer will be updated every time a character is traversed. code show as below:

import java.util.Scanner;
class Solution {
   public int longestSemiAlternatingSubstring(String s) {
        // write your code here
        int res = 0, count = 0;
        char ch = 0;
        
        for (int i = 0, j = 0; i < s.length(); i++) {
            if (i == 0 || s.charAt(i) != ch) {
                ch = s.charAt(i);
                count = 1;
            } else {
                count++;
                if (count >= 3) {
                    j = i - 1;
                }
            }
            
            res = Math.max(res, i - j + 1);
        }
        
        return res;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
 
        int res = longestSemiAlternatingSubstring(s);
        System.out.println(res);
    }
}

Program C++:

This question is similar to String Without 3 Identical Consecutive Letters but here we need to find a longest substring which doesn’t contain three identical consecutive characters and return it’s length.

#include <iostream>
#include <string>

using namespace std;

int solution(const string & s) {
    const int MAX_COUNT = 3;
    int s_len = s.length();
    if(s_len < MAX_COUNT) { return s_len; }
    int count = 1, result = 1;
    // Scan whole string and count it's characters.
    for(int i = 1; i < s_len - 1; ++i) {
        // If we meet 3 consecutive characters
        if((s[i-1] == s[i]) && (s[i+1] == s[i])) {
            // save the counter as result if it is bigger than the previous result
            result = max(result,count+1);
            // and drop the counter to 1
            count = 1;
        }
        else { count++; }
    }
    // return maximal result
    return max(result,count+1);
}

int main() {
    cout << solution("baaabbabbb") << " Expected: 7" << endl;
    cout << solution("babba") << " Expected: 5" << endl;
    cout << solution("abaaaa") << " Expected: 4" << endl;


    cout << solution("eedaaad") << endl;
    cout << solution("xxxtxxx") << endl;
    cout << solution("uuuuxaaaaxuuu") << endl;
    return 0;
}

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA Online Assessment 2021 Questions and Answers

Microsoft Online Assessment 2021 Questions

Leave a Comment