Original Problem


  • The idea here is to maintain 2 Stack, one for lowercase, one for uppercase. The stack keeps track the index of the elements that aren’t b or B
  • When we see a b or B, we just delete the first element from the corresponding stack by replacing the element at that index with either b or B
  • Then we loop the original string, add characters that aren’t b and B to form a new string which is the final answer

Space & Time Analysis

The analysis method we are using is Algorithm Complexity Analysis

Space - O(n)

  • Ignore input size & language dependent space
  • We are maintaining 2 Stack

Time - O(n)

  • One loop to serialise the given string
  • One loop to form the final answer string


1st Attempt (Java)

import java.util.Scanner;
import java.util.Stack;
public class Solution {
  public static void main(String[] args) {
    // Read input meta data
    Scanner scanner = new Scanner(System.in);
    int t = scanner.nextInt();
    for (int i=0; i<t; i++) {
      char[] s = scanner.nextLine().toCharArray();
      Stack<Integer> lowerCase = new Stack<>();
      Stack<Integer> upperCase = new Stack<>();
      for (int j=0; j<s.length; j++) {
        if (s[j] == 'b' && lowerCase.size() > 0) {
          s[lowerCase.pop()] = 'b';
        if (s[j] == 'B' && upperCase.size() > 0) {
          s[upperCase.pop()] = 'B';
        if (s[j] >= 'a' && s[j] <= 'z') {
        } else {
      StringBuilder sb = new StringBuilder();
      for (int j=0; j<s.length; j++) {
        if (s[j] != 'B' && s[j] != 'b') sb.append(s[j]);

Personal Reflection

  • Why it takes so long to solve: NIL
  • What you could have done better: NIL
  • What you missed: NIL
  • Ideas you’ve seen before: Stack, last in first out property
  • Ideas you found here that could help you later: Understand the properties of Data Structure well
  • Ideas that didn’t work and why: NIL