Min Deletions To Obtain String in Right Format - Company-specific OAs / Microsoft OA

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()))
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

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Introduction

DFS on Tree

Binary Search Tree

Combinatorial Search

Memoization

Pruning

Dedup

Additional Practices

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Sequence

Grid

Dynamic number of subproblems

Partition

Game Theory

Interval

Two Sequences

0-1 Knapsack

Bitmask

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Composite Patterns

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

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

Example 1:

Input:YXXXYXY

Output: 2

Explanation:

Example 2:

Input:YYXYXX

Output: 3

Explanation:

Example 3:

Input:XXYYYY

Output: 0

Explanation:

Try it yourself

Implementation

Input:`YXXXYXY`

Output: `2`

Input:`YYXYXX`

Output: `3`

Input:`XXYYYY`

Output: `0`