Beautiful Strings — Asked in Microsoft, Adobe and Intuit Interviews

Problem Statement :

Ninja has been given a binary string ‘STR’ containing either ‘0’ or ‘1’. A binary string is called beautiful if it contains alternating 0s and 1s. He wants to make ‘STR’ beautiful by performing some operations on it. In one operation, Ninja can convert ‘0’ into ‘1’ or vice versa.

Your task is to determine the minimum number of operations Ninja should perform to make ‘STR’ beautiful.

Given :

01011

Output :

1

Explanation of given Test Cases :

The two beautiful strings that can be formed from the given ‘STR’ are “10101” and “01010”. Ninja can transform ‘STR’ to “10101” by performing the following operations: Replace ‘0’ at index 0 by ‘1’. Replace ‘1’ at index 1 by ‘0’. Replace ‘0’ at index 2 by ‘1’ Replace ‘1’ at index 4 by ‘0’. Ninja can transform ‘STR’ to “01010” by performing the following operations: Replace ‘1’ at index 4 by ‘0’. The minimum number of operations in transforming ‘STR’ to beautiful is the minimum of the above two which is 1.

Approach :

We observe that for any length of the given string ‘STR’, there are only two possible beautiful strings ie: one starting with ‘1’ and the other starting with ‘0’.

For example for ’N’ = 4 , “1010” and “0101” are the only two possible beautiful strings.

Now, we just need to count the different values at the same index in a possible beautiful string and given ’STR’.

For example: If ‘STR’ = “1011”, there exist two beautiful strings of length 4 ie: “1010” and “0101”. The count of different values at same index in ‘STR’ and “1010” is 1 and ‘STR’ and “0101” is 3 respectively and 1 is the minimum of these two so we need only ‘1’ operation to convert ‘1011’ to ‘1010’.

Algorithm:

Initialize four variables ‘T1’ = 0, ‘T2’ = 0,’S1’ = 0’ and ‘S2’ = 1 where ‘T1’ denotes the difference between values at indices in ‘STR’ and the possible beautiful string starting with 0 and ‘T2’ denotes the difference between values at indices in ‘STR’ and the possible beautiful string starting with 1.‘S1’ and ‘S2’ denote the expected value at index ‘i’ in both of the possible beautiful strings

Iterate the given string ‘STR’ and do the following:

• If ‘STR[i]’ == 1
• If ‘S1’ == 0’ then T1++.
• Else T2++.
• If ‘STR[i]’ == 0
• If ‘S1’ == 1 then T1++.
• Else T2++
• If ‘S1’ == 0’ then make it 1 and vise versa do the same for ‘S2’.
• Finally return the minimum of ‘T1’ and ‘T2’.

Time Complexity : O(|STR|)
Space Complexity : O(1)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.