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
1def min_step(s: str) -> int:
2 num_y = 0
3 min_del = 0
4 for c in s:
5 if c == "X":
6 min_del = min(num_y, min_del + 1)
7 else:
8 num_y += 1
9 return min_del
10
11if __name__ == "__main__":
12 s = input()
13 res = min_step(s)
14 print(res)
151import java.util.Scanner;
2
3class Solution {
4 public static int minStep(String s) {
5 int numY = 0;
6 int minDel = 0;
7 for (int i = 0; i < s.length(); i++) {
8 if (s.charAt(i) == 'X') {
9 minDel = Math.min(numY, minDel + 1);
10 } else {
11 numY++;
12 }
13 }
14 return minDel;
15 }
16
17 public static void main(String[] args) {
18 Scanner scanner = new Scanner(System.in);
19 String s = scanner.nextLine();
20 scanner.close();
21 int res = minStep(s);
22 System.out.println(res);
23 }
24}
251"use strict";
2
3function minStep(s) {
4 let numY = 0;
5 let minDel = 0;
6 for (const c of s) {
7 if (c === "X") {
8 minDel = Math.min(numY, minDel + 1);
9 } else {
10 numY++;
11 }
12 }
13 return minDel;
14}
15
16function* main() {
17 const s = yield;
18 const res = minStep(s);
19 console.log(res);
20}
21
22class EOFError extends Error {}
23{
24 const gen = main();
25 const next = (line) => gen.next(line).done && process.exit();
26 let buf = "";
27 next();
28 process.stdin.setEncoding("utf8");
29 process.stdin.on("data", (data) => {
30 const lines = (buf + data).split("\n");
31 buf = lines.pop();
32 lines.forEach(next);
33 });
34 process.stdin.on("end", () => {
35 buf && next(buf);
36 gen.throw(new EOFError());
37 });
38}
39