Min Deletions To Obtain String in Right Format

Given a string S of length N consisting only of letters A and/or B. Our goal is to obtain a string in the format A...AB...B (all letters A occur before all letters B) by deleting some letters from S. In particular, strings consisting only of letters A or only of letters B fit this format.

Given a string S, returns the minimum number of letters that need to be deleted from S in order to obtain a string in the A...AB...B format.

Example 1:

Input:BAAABAB

Output: 2

Explanation:

We can obtain AAABB by:

  • Delete first B -> AAABAB
  • Delete last occurance pf A -> AAABB

Example 2:

Input:BBABAA

Output: 3

Explanation:

We can remove all occurrence of A or B:

Example 3:

Input:WR

Output: -1

Explanation:

The minimum needed number of swaps is greater than 10^9. So return -1.

Example 4:

Input:AABBBB

Output: 0

Explanation:

String matches the format required.

Try it yourself

Implementation

1
1
def minStep(str) -> int:
2
-
      # WRITE YOUR BRILLIANT CODE HERE
2
+
      charA = 'A';
3
+
      numB = 0;
4
+
      minDel = 0;
5
+
      for i in range(0, len(str)):
6
+
          if (charA == str[i]):
7
+
              minDel = min(numB, minDel + 1);
8
+
          else:
9
+
              numB = numB + 1;
10
+
      return minDel;
3
11
if __name__ == '__main__':
4
12
    print(minStep(input()))