Longest Semi-Alternating Substring Microsoft OA 2023

Contents

1 Longest Semi-Alternating Substring Solution
- 1.1 SOLUTION
2 Microsoft Online Assessment 2023 Questions List

Longest Semi-Alternating Substring Solution

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.

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: Longest Semi-Alternating Substring Solution in 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: Longest Semi-Alternating Substring Solution in 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: Longest Semi-Alternating Substring Solution in 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;
}

Longest Semi-Alternating Substring Solution

SOLUTION

Microsoft Online Assessment 2023 Questions List

Leave a Comment Cancel reply