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 of X -> XXXYY

Example 2:

Input:YYXYXX

Output: 3

Explanation:

We can remove all occurrences 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
1import 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}
27
1const 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});
27

Got 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.

←
↑TA 👨‍🏫