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
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()))
141import java.util.*;
2
3class Solution {
4 public static int minStep(String str) {
5 int charX = 'X';
6 int numY = 0;
7 int minDel = 0;
8
9 for (int i = 0; i < str.length(); i++) {
10 if (charX == str.charAt(i)) {
11 minDel = Math.min(numY, minDel + 1);
12 } else {
13 numY++;
14 }
15 }
16 return minDel;
17 }
18
19 public static void main(String[] args) {
20 Scanner scanner = new Scanner(System.in);
21 String str = scanner.nextLine();
22 scanner.close();
23 System.out.println(minStep(str));
24 }
25
26}
271const readline = require('readline');
2
3function minStep(str) {
4 const charX = 'X';
5 let numY = 0;
6 let minDel = 0;
7
8
9 for (let i = 0; i < str.length; i++) {
10 if (charX === str[i]) {
11 minDel = Math.min(numY, minDel + 1);
12 } else {
13 numY++;
14 }
15 }
16 return minDel;
17}
18
19const rl = readline.createInterface(process.stdin);
20const inputs = [];
21rl.on('line', (input) => {
22 input !== '' ? inputs.push(input) : rl.close();
23}).on('close', () => {
24 rl.close();
25 console.log(minStep(inputs[0]));
26});
27Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.