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.

  • 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];
    };
    
    

All Problems

All Solutions