Question

Microsoft | OA Coding Questions and Solutions | Set - 58 | 2022

Answer 1

Images of ques

Answer 2

Solved in Python3 solution.
Approaches:

 

1. Make groups by their lengths
2. Keep maximum lengths from groups
3. Accumulate sum of difference max lengths from other groups lengths

 

O(N) time & space.

 

def solution(s: str) -> int:
    if not s:
        return 0
    
    groups = []
    prev, count = s[0], 1
    max_len = 0
    for c in s[1:]:
        if c == prev:
            count += 1
        else:
            groups.append(count)
            count = 1
            prev = c
        max_len = max(max_len, count)
    groups.append(count)
    max_len = max(max_len, count)
    
    return sum(max_len - group for group in groups)

print(solution("babaa")) # 3
print(solution("bbbab")) # 4
print(solution("bbbaaabbb")) # 0

Answer 3

Python solution

 

def solution(s: str) -> int:
	if not s:
		return 0
	counts, p = [], 0

	for i in range(1, len(s)):
		if s[i] != s[p]:
			counts.append(i-p)
			p = i

	counts.append(len(s)-p)
	high = max(counts)
	return sum([high - x for x in counts])

Answer 4

JAVA solution:

 

public static int numOfLettersToAdd(String s)
{
if (s.length() < 3)
return 0;
int appear = 1;
int max_appear = 1;
int num_groups = 1;
int num_chars = 0;
char prev = s.charAt(0);

 

	for (int i = 1; i < s.length(); i++)
	{
		if(s.charAt(i) != prev)
		{
			if (appear > max_appear)
				max_appear = appear;
			num_groups++;
			appear = 1;
		}
		else
			appear++;
		
		prev = s.charAt(i);
	}
	if (appear > max_appear) //if biggest group is the rightmost
		max_appear = appear;
	
	num_chars = s.length() - max_appear;
	return ((num_groups - 1) * max_appear) - num_chars ;
}

Answer 5

Java code in O(n) time and O(1) space:

 

 public static int equaliseBlocks(String s)
    {
        int maxBlock = Integer.MIN_VALUE;
        maxBlock = findMaxBlock(s);
        int ans = 0;
        int cnt = 1;
        for(int i=1;i<s.length();i++)
        {
            char c = s.charAt(i);
            char last = s.charAt(i-1);
            if(c==last) cnt++;
            else
            {

                ans = ans + maxBlock - cnt;
                cnt = 1;
            }
            if(i==s.length()-1) {
                ans = ans + maxBlock - cnt;
            }
        }

        return ans;
    }

//Calculate max block size
    public static int findMaxBlock(String s)
    {
        int max = Integer.MIN_VALUE;
        int cnt = 1;
        for(int i=1;i<s.length();i++)
        {
            char c = s.charAt(i);
            char last = s.charAt(i-1);
            if(c==last) cnt++;
            else
            {
                max = Math.max(max, cnt);
                cnt = 1;
            }
            if(i==s.length()-1) {
                max = Math.max(max, cnt);
            }
        }
        return max;
    }

Answer 6

O(n) time and O(1) space

 

Calculate sum of all block size , total number of blocks and size of largest block.
Then ans = (size of largest block * total number of blocks) - sum of all block size
All these in a single loop.

 

int solution(string &s){
int maxb=1;
int totalb=0;
int sumbSizes=0;
int curr_size=1;
int i=1;
int n=s.size();

 

for(int i=1;i<n;i++){
    if(s[i]==s[i-1]){
        curr_size++;
    }
    else{
        sumbSizes=sumbSizes+curr_size;
        totalb++;
        maxb=max(maxb,curr_size);
        curr_size=1;
    }
}
sumbSizes=sumbSizes+curr_size;
totalb++;
 maxb=max(maxb,curr_size);
return ((maxb*totalb)-sumbSizes);

 

}

Answer 7

Keep track of block of same characters using two pointer approach. Incrementing j till s[i] == s[j]. Also, keep track of max length of the block.
Minimum characters required to add to the current string is basically maxLen * number_of_blocks - length_of_input_string

 

int solution(string s){
    int i = 0;
    int j = 0;
    int count = 0;
    int maxLen = INT_MIN;
    for(;j<s.size();){
        if(s[i] == s[j]){
            j++;
        }else{
            maxLen = max(maxLen, j - i);
            count++;
            i = j;
            j++;
        }
    }
    maxLen = max(maxLen, j - i);
    return maxLen * (count+1)  - s.size();
}

Answer 8

My Solution :

 

int solution(string &S) {
   int count=1;
    int max=1;
    int n = S.length();
    if(n==0 || n==1){
        return 0;
    }
   int ans[100]={0};
    int x=0;
    ans[x]=count;
    for(int i=1;i<n;i++){
        if(S[i]==S[i-1]){
            count++;
            ans[x]=count;
            if(max<count){
                max=count;
            }
        }else{
            count=1;
            x++;
            ans[x]=count;
        }
    }
    int result=0;
    int m = sizeof(ans)/sizeof(ans[0]);
    for(int i=0;i<m;i++){
        if(ans[i]!=0){
            int t=(max-ans[i]);
            result=result+t;
        }
        else{
            break;
        }
    }
    return result;
}

 

Code passed all the test cases, but the performance score was low. Can anyone suggest optimized space approach?