Welcome to Subscribe On Youtube

2696. Minimum String Length After Removing Substrings

Description

You are given a string s consisting only of uppercase English letters.

You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings "AB" or "CD" from s.

Return the minimum possible length of the resulting string that you can obtain.

Note that the string concatenates after removing the substring and could produce new "AB" or "CD" substrings.

 

Example 1:

Input: s = "ABFCACDB"
Output: 2
Explanation: We can do the following operations:
- Remove the substring "ABFCACDB", so s = "FCACDB".
- Remove the substring "FCACDB", so s = "FCAB".
- Remove the substring "FCAB", so s = "FC".
So the resulting length of the string is 2.
It can be shown that it is the minimum length that we can obtain.

Example 2:

Input: s = "ACBBD"
Output: 5
Explanation: We cannot do any operations on the string so the length remains the same.

 

Constraints:

• 1 <= s.length <= 100
• s consists only of uppercase English letters.

Solutions

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• class Solution {
      public int minLength(String s) {
          Deque<Character> stk = new ArrayDeque<>();
          stk.push(' ');
          for (char c : s.toCharArray()) {
              if ((c == 'B' && stk.peek() == 'A') || (c == 'D' && stk.peek() == 'C')) {
                  stk.pop();
              } else {
                  stk.push(c);
              }
          }
          return stk.size() - 1;
      }
  }
  

• class Solution {
  public:
      int minLength(string s) {
          string stk = " ";
          for (char& c : s) {
              if ((c == 'B' && stk.back() == 'A') || (c == 'D' && stk.back() == 'C')) {
                  stk.pop_back();
              } else {
                  stk.push_back(c);
              }
          }
          return stk.size() - 1;
      }
  };
  

• class Solution:
      def minLength(self, s: str) -> int:
          stk = [""]
          for c in s:
              if (c == "B" and stk[-1] == "A") or (c == "D" and stk[-1] == "C"):
                  stk.pop()
              else:
                  stk.append(c)
          return len(stk) - 1
  
  

• func minLength(s string) int {
  	stk := []byte{' '}
  	for _, c := range s {
  		if (c == 'B' && stk[len(stk)-1] == 'A') || (c == 'D' && stk[len(stk)-1] == 'C') {
  			stk = stk[:len(stk)-1]
  		} else {
  			stk = append(stk, byte(c))
  		}
  	}
  	return len(stk) - 1
  }
  

• function minLength(s: string): number {
      const stk: string[] = [''];
      for (const c of s) {
          if (c === 'B' && stk[stk.length - 1] === 'A') {
              stk.pop();
          } else if (c == 'D' && stk[stk.length - 1] === 'C') {
              stk.pop();
          } else {
              stk.push(c);
          }
      }
      return stk.length - 1;
  }
  
  

• impl Solution {
      pub fn min_length(s: String) -> i32 {
          let mut ans: Vec<u8> = Vec::new();
  
          for c in s.bytes() {
              if let Some(last) = ans.last() {
                  if *last == b'A' && c == b'B' {
                      ans.pop();
                  } else if *last == b'C' && c == b'D' {
                      ans.pop();
                  } else {
                      ans.push(c);
                  }
              } else {
                  ans.push(c);
              }
          }
  
          ans.len() as i32
      }
  }
  

All Problems

All Solutions