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 X
s 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
2def minStep(str) -> int:
3 charX = 'X';
4 numY = 0;
5 minDel = 0;
6 for i in range(0, len(str)):
7 if (charX == str[i]):
8 minDel = min(numY, minDel + 1);
9 else:
10 numY = numY + 1;
11 return minDel;
12if __name__ == '__main__':
13 print(minStep(input()))
14