2516. Take K of Each Character From Left and Right

Take K of Each Character From Left and Right (LeetCode 2516) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.

How to solve Take K of Each Character From Left and Right

Take K of Each Character From Left and Right is a Variable Size Sliding Window problem, part of Sliding Window. Master variable-size sliding window for condition-based problems like longest substring without repeating characters.

Work towards the solution in these steps:

1. Start by counting the frequency of each character and checking if it is possible.
2. If you take x characters from the left side, what is the minimum number of characters you need to take from the right side? Find this for all values of x in the range 0 ≤ x ≤ s.length.
3. Use a two-pointers approach to avoid computing the same information multiple times.

The reference solution runs in O(n) time and O(1) space.

The Take K of Each Character From Left and Right solution and editorial walks through the full approach with reference code.

Problem statement

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

Topics and companies

Topics: Hash Table, String, Sliding Window.

How to practise Take K of Each Character From Left and Right on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Take K of Each Character From Left and Right in the code editor, or read the Take K of Each Character From Left and Right editorial for a worked solution with its approach and complexity analysis.

Where Take K of Each Character From Left and Right sits in the DSA pattern sheet

• Sliding Window pattern guide
• Variable Size (Condition-Based) subpattern
• The full DSA patterns sheet

Problems related to Take K of Each Character From Left and Right

Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:

• Contains Duplicate II — Easy, same subpattern
• Continuous Subarrays — Medium, same subpattern
• Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
• Frequency of the Most Frequent Element — Medium, same subpattern
• Fruit Into Baskets — Medium, same subpattern
• Jump Game VII — Medium, same subpattern

Take K of Each Character From Left and Right FAQ