Welcome to Subscribe On Youtube

1653. Minimum Deletions to Make String Balanced

Description

You are given a string s consisting only of characters 'a' and 'b'​​​​.

You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.

Return the minimum number of deletions needed to make s balanced.

 

Example 1:

Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").

Example 2:

Input: s = "bbaaaaabb"
Output: 2
Explanation: The only solution is to delete the first two characters.

 

Constraints:

• 1 <= s.length <= 105
• s[i] is 'a' or 'b'​​.

Solutions

Dynamic programming.

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• Java 2
• C++ 2
• Python 2
• Go 2
• TypeScript 2
• Javascript 2

• class Solution {
      public int minimumDeletions(String s) {
          int n = s.length();
          int[] f = new int[n + 1];
          int b = 0;
          for (int i = 1; i <= n; ++i) {
              if (s.charAt(i - 1) == 'b') {
                  f[i] = f[i - 1];
                  ++b;
              } else {
                  f[i] = Math.min(f[i - 1] + 1, b);
              }
          }
          return f[n];
      }
  }
  

• class Solution {
  public:
      int minimumDeletions(string s) {
          int n = s.size();
          int f[n + 1];
          memset(f, 0, sizeof(f));
          int b = 0;
          for (int i = 1; i <= n; ++i) {
              if (s[i - 1] == 'b') {
                  f[i] = f[i - 1];
                  ++b;
              } else {
                  f[i] = min(f[i - 1] + 1, b);
              }
          }
          return f[n];
      }
  };
  

• class Solution:
      def minimumDeletions(self, s: str) -> int:
          n = len(s)
          f = [0] * (n + 1)
          b = 0
          for i, c in enumerate(s, 1):
              if c == 'b':
                  f[i] = f[i - 1]
                  b += 1
              else:
                  f[i] = min(f[i - 1] + 1, b)
          return f[n]
  
  

• func minimumDeletions(s string) int {
  	n := len(s)
  	f := make([]int, n+1)
  	b := 0
  	for i, c := range s {
  		i++
  		if c == 'b' {
  			f[i] = f[i-1]
  			b++
  		} else {
  			f[i] = min(f[i-1]+1, b)
  		}
  	}
  	return f[n]
  }
  

• function minimumDeletions(s: string): number {
      const n = s.length;
      const f = new Array(n + 1).fill(0);
      let b = 0;
      for (let i = 1; i <= n; ++i) {
          if (s.charAt(i - 1) === 'b') {
              f[i] = f[i - 1];
              ++b;
          } else {
              f[i] = Math.min(f[i - 1] + 1, b);
          }
      }
      return f[n];
  }
  
  

• /**
   * @param {string} s
   * @return {number}
   */
  var minimumDeletions = function (s) {
      const n = s.length;
      const f = new Array(n + 1).fill(0);
      let b = 0;
      for (let i = 1; i <= n; ++i) {
          if (s[i - 1] === 'b') {
              f[i] = f[i - 1];
              ++b;
          } else {
              f[i] = Math.min(f[i - 1] + 1, b);
          }
      }
      return f[n];
  };
  
  

• class Solution {
      public int minimumDeletions(String s) {
          int lb = 0, ra = 0;
          int n = s.length();
          for (int i = 0; i < n; ++i) {
              if (s.charAt(i) == 'a') {
                  ++ra;
              }
          }
          int ans = n;
          for (int i = 0; i < n; ++i) {
              ra -= (s.charAt(i) == 'a' ? 1 : 0);
              ans = Math.min(ans, lb + ra);
              lb += (s.charAt(i) == 'b' ? 1 : 0);
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int minimumDeletions(string s) {
          int lb = 0, ra = count(s.begin(), s.end(), 'a');
          int ans = ra;
          for (char& c : s) {
              ra -= c == 'a';
              ans = min(ans, lb + ra);
              lb += c == 'b';
          }
          return ans;
      }
  };
  

• class Solution:
      def minimumDeletions(self, s: str) -> int:
          lb, ra = 0, s.count('a')
          ans = len(s)
          for c in s:
              ra -= c == 'a'
              ans = min(ans, lb + ra)
              lb += c == 'b'
          return ans
  
  

• func minimumDeletions(s string) int {
  	lb, ra := 0, strings.Count(s, "a")
  	ans := ra
  	for _, c := range s {
  		if c == 'a' {
  			ra--
  		}
  		if t := lb + ra; ans > t {
  			ans = t
  		}
  		if c == 'b' {
  			lb++
  		}
  	}
  	return ans
  }
  

• function minimumDeletions(s: string): number {
      let lb = 0,
          ra = 0;
      let n = s.length;
      for (let i = 0; i < n; ++i) {
          if (s[i] === 'a') {
              ++ra;
          }
      }
      let ans = n;
      for (let i = 0; i < n; ++i) {
          ra -= s[i] === 'a' ? 1 : 0;
          ans = Math.min(ans, lb + ra);
          lb += s[i] === 'b' ? 1 : 0;
      }
      return ans;
  }
  
  

• /**
   * @param {string} s
   * @return {number}
   */
  var minimumDeletions = function (s) {
      let lb = 0,
          ra = 0;
      let n = s.length;
      for (let i = 0; i < n; ++i) {
          if (s[i] === 'a') {
              ++ra;
          }
      }
      let ans = n;
      for (let i = 0; i < n; ++i) {
          ra -= s[i] === 'a' ? 1 : 0;
          ans = Math.min(ans, lb + ra);
          lb += s[i] === 'b' ? 1 : 0;
      }
      return ans;
  };
  
  

All Problems

All Solutions