Microsoft Online Assessment (OA) - Min Deletions To Obtain String in Right Format

Given a string with only characters X and Y. Find the minimum number of characters to remove from the string such that there is no interleaving of character X and Y and all the Xs appear before any Y.

Example 1:

Input:YXXXYXY

Output: 2

Explanation:

We can obtain XXXYY by:

  • Delete first Y -> XXXYXY
  • Delete last occurrence pf X -> XXXYY

Example 2:

Input:YYXYXX

Output: 3

Explanation:

We can remove all occurrence of X or Y:

Example 3:

Input:XXYYYY

Output: 0

Explanation:

String matches the format required.

Try it yourself

Implementation

1
1
def minStep(str) -> int:
2
-
      # WRITE YOUR BRILLIANT CODE HERE
2
+
      charX = 'X';
3
+
      numY = 0;
4
+
      minDel = 0;
5
+
      for i in range(0, len(str)):
6
+
          if (charX == str[i]):
7
+
              minDel = min(numY, minDel + 1);
8
+
          else:
9
+
              numY = numY + 1;
10
+
      return minDel;
3
11
if __name__ == '__main__':
4
12
    print(minStep(input()))