Scale Engineer

Take K of Each Character From Left and Right

Med
#2296Time: O(N^2), where N is the length of the string. The nested loops iterate up to N times each.Space: O(1) extra space, as we only store counts for three characters.
Patterns
Sliding Window
Data structures
Hash TableString

Prompt

You are given a string s consisting of the characters 'a', 'b', and 'c' and a non-negative integer k. Each minute, you may take either the leftmost character of s, or the rightmost character of s.

Return the minimum number of minutes needed for you to take at least k of each character, or return -1 if it is not possible to take k of each character.

 

Example 1:

Input: s = "aabaaaacaabc", k = 2
Output: 8
Explanation: 
Take three characters from the left of s. You now have two 'a' characters, and one 'b' character.
Take five characters from the right of s. You now have four 'a' characters, two 'b' characters, and two 'c' characters.
A total of 3 + 5 = 8 minutes is needed.
It can be proven that 8 is the minimum number of minutes needed.

Example 2:

Input: s = "a", k = 1
Output: -1
Explanation: It is not possible to take one 'b' or 'c' so return -1.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of only the letters 'a', 'b', and 'c'.
  • 0 <= k <= s.length

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into a solution by checking every possible combination of characters taken from the left and right. We iterate through every possible prefix length and, for each, find the shortest suffix that, when combined with the prefix, satisfies the condition of having at least k of each character.

Algorithm

  1. First, handle the edge cases. If the total count of any character in s is less than k, it's impossible, so return -1. If k is 0, no characters need to be taken, so return 0.
  2. Initialize minMinutes to the length of the string n, which is the maximum possible answer.
  3. Iterate through all possible prefix lengths i from 0 to n.
  4. For each i, calculate the counts of 'a', 'b', and 'c' in the prefix s[0...i-1].
  5. Then, for the current prefix, iterate through all possible suffix lengths j from 0 to n-i.
  6. In this inner loop, incrementally build the suffix counts. For each j, add the character s[n-j] to the suffix counts.
  7. Combine the prefix and suffix counts. Check if the counts of 'a', 'b', and 'c' are all at least k.
  8. If the condition is met, we have found a valid combination of i characters from the left and j from the right. The total minutes are i + j. We update minMinutes = min(minMinutes, i + j).
  9. Since we are iterating j from smallest to largest, the first j that satisfies the condition for a given i will be the smallest. We can break the inner loop to optimize slightly.
  10. After checking all i, minMinutes will hold the minimum total characters needed.

Walkthrough

The brute-force method involves a nested loop structure. The outer loop iterates through all possible numbers of characters to take from the left, let's say i. The inner loop iterates through all possible numbers of characters to take from the right, j. For each pair (i, j), we must ensure we don't take more characters than available (i + j <= n). We then count the characters in the chosen prefix and suffix and check if they meet the k requirement. To avoid re-calculating counts repeatedly, which would lead to an O(N^3) solution, we can calculate the prefix counts once per outer loop iteration and incrementally update the suffix counts in the inner loop. This optimization brings the complexity down to O(N^2).

class Solution {    public int takeCharacters(String s, int k) {        int n = s.length();        int[] totalCounts = new int[3];        for (char c : s.toCharArray()) {            totalCounts[c - 'a']++;        }        if (totalCounts[0] < k || totalCounts[1] < k || totalCounts[2] < k) {            return -1;        }        if (k == 0) return 0;         int minMinutes = n;        // i = number of chars from left        for (int i = 0; i <= n; i++) {            int[] prefixCounts = new int[3];            for (int p = 0; p < i; p++) {                prefixCounts[s.charAt(p) - 'a']++;            }                        int[] suffixCounts = new int[3];            // j = number of chars from right            for (int j = 0; j <= n - i; j++) {                if (j > 0) {                    suffixCounts[s.charAt(n - j) - 'a']++;                }                                if (prefixCounts[0] + suffixCounts[0] >= k &&                    prefixCounts[1] + suffixCounts[1] >= k &&                    prefixCounts[2] + suffixCounts[2] >= k) {                    minMinutes = Math.min(minMinutes, i + j);                    break; // Smallest j for this i is found                }            }        }        return minMinutes;    }}

Complexity

Time

O(N^2), where N is the length of the string. The nested loops iterate up to N times each.

Space

O(1) extra space, as we only store counts for three characters.

Trade-offs

Pros

  • The logic is straightforward and follows directly from the problem description.

  • It is relatively easy to implement.

Cons

  • The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will likely result in a 'Time Limit Exceeded' error.

Solutions

class Solution { public int takeCharacters ( String s , int k ) { int [] cnt = new int [ 3 ]; int n = s . length (); for ( int i = 0 ; i < n ; ++ i ) { ++ cnt [ s . charAt ( i ) - 'a' ]; } if ( cnt [ 0 ] < k || cnt [ 1 ] < k || cnt [ 2 ] < k ) { return - 1 ; } int ans = 0 , j = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int c = s . charAt ( i ) - 'a' ; -- cnt [ c ]; while ( cnt [ c ] < k ) { ++ cnt [ s . charAt ( j ++) - 'a' ]; } ans = Math . max ( ans , i - j + 1 ); } return n - ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem