Maximum Number of Removable Characters Solution in C++/Java/Python/JS
Maximum Number of Removable Characters Problem Description:
You are given two strings s and p where p is a subsequence of s. You are also given a distinct 0-indexed integer array removable containing a subset of indices of s (s is also 0-indexed).
You want to choose an integer k (0 <= k <= removable.length) such that, after removing k characters from s using the first k indices in removable, p is still a subsequence of s. More formally, you will mark the character at s[removable[i]] for each 0 <= i < k, then remove all marked characters and check if p is still a subsequence.
Return the maximum k you can choose such that p is still a subsequence of s after the removals.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
Examples :
Input: s = "abcacb", p = "ab", removable = [3,1,0]
Output: 2
Explanation: After removing the characters at indices 3 and 1, "abcacb" becomes "accb".
"ab" is a subsequence of "accb".
If we remove the characters at indices 3, 1, and 0, "abcacb" becomes "ccb", and "ab" is no longer a subsequence.
Hence, the maximum k is 2.
Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
Output: 1
Explanation: After removing the character at index 3, "abcbddddd" becomes "abcddddd".
"abcd" is a subsequence of "abcddddd".
Input: s = "abcab", p = "abc", removable = [0,1,2,3,4]
Output: 0
Explanation: If you remove the first index in the array removable, "abc" is no longer a subsequence.
Constraints:
1 <= p.length <= s.length <= 10⁵
0 <= removable.length < s.length
0 <= removable[i] < s.length
p is a subsequence of s.
s and p both consist of lowercase English letters.
The elements in removable are distinct.
Brute Force Approach
To approach the problem, we are given two strings s and p, where p is a subsequence of s. We are also given a distinct 0-indexed integer array removable that contains indices of characters in s which can be removed. Our goal is to determine the maximum possible value of k (0 <= k <= removable.length) such that after removing k characters from s using the first k indices in removable, p is still a subsequence of s.
What can be the minimum value of k?
The minimum value required should be 0 because initially, before any removal, p is already a subsequence of s. This means that in the worst case, if removing even one character prevents p from being a subsequence, k = 0 is the answer.
Now that we know the minimum value of k, what would be the maximum value of k?
The maximum possible value of k should be removable.length. This is because, in the best case, if we can remove all the characters at indices in removable while still keeping p as a subsequence, then k can reach its highest possible value.
Thus, our search space for the answer ranges from 0 to removable.length. Now, the problem reduces to finding the largest k such that p remains a subsequence of s after removing the first k indices from removable.
A basic approach is to iterate through all possible values from 0 to removable.length and check whether p is still a subsequence after removing those k indices. If it is possible, then k is a valid solution. We continue this process until we find the maximum valid k where p is still a subsequence but is no longer valid for k + 1.
The idea is to start from 0 to removable.length and stop whenever we find the point where it's not possible to keep p as a subsequence, and return the point before it, as it was the maximum valid k.
Consider s = "abcacb", p = "ab", removable = [3,1,0].
We start by setting the smallest possible k as 0 and the largest possible k as removable.length = 3. We then check how p behaves for different values of k:
- If k = 0, p is still a subsequence of s.
- If k = 1, we remove s[3], so s becomes "abcacb", and p is still a subsequence.
- If k = 2, we remove s[3] and s[1], so s becomes "accb", and p is still a subsequence.
- If k = 3, we remove s[3], s[1], and s[0], so s becomes "ccb", and p is no longer a subsequence.
Since 3 is the first point where p is no longer a subsequence, we return 2, the point before it.
Thus, the answer is 2.
We can see that every number from 0 to 2 allows p to remain a subsequence. But as soon as we try 3 or more, p is no longer a subsequence.
Let's call the maximum possible k as maxK. Any number from maxK + 1 to removable.length won’t work because it will always remove necessary characters of p, making it impossible to be a subsequence. However, any number from 0 to maxK will allow p to remain a subsequence.
Therefore, maxK is the largest possible k such that p is still a subsequence of s after removing k indices from removable. Any number from 0 to maxK will work, but as soon as we try maxK + 1 or more, it won’t be possible anymore.
Explaining the Subsequence Check Process in Real-World Terms
Imagine you have a text document (s) with a highlighted phrase (p) that must remain visible as a continuous block. You also have an eraser (removable) that allows you to erase specific characters from s. Your goal is to figure out how many characters you can erase while still keeping p visible in one complete piece.
Step 1: Understanding How Much We Can Remove
We need to check if p is still visible after removing a certain number of characters from s. This number is represented by k, which tells us how many characters we erase.
- If k is too large, we might remove crucial parts of s, causing p to disappear.
- If k is too small, we are not maximizing how many characters we can erase while still keeping p visible.
Step 2: Modifying the String to Reflect the Removal
To check if p remains a substring after removing the first k indices from removable, we follow these steps:
- Mark all indices corresponding to the first k elements in removable with a special character (like '#'). This simulates erasing those characters without shifting the remaining characters around.
- Look at the modified s and check if p still appears as a continuous block.
- If p appears as it is, then p is still a substring of s.
- If p does not appear as a continuous block, it means p is no longer a substring.
Step 3: Checking for a Valid k
To determine whether p is still a substring of the modified s, we use two pointers:
- Pointer i starts at the beginning of s.
- Pointer j starts at the beginning of p.
- We move i through s, skipping characters marked as '#' (erased characters).
- If we find a match between s[i] and p[j], we move both pointers forward (i++ and j++).
- If the characters don’t match, we simply move i forward to check if p can still be found later in s.
If we can move through p completely without skipping any necessary character, then p is still a substring after removing k characters.
Step 4: Finding the Maximum Possible k
We gradually increase k to find the maximum value where p is still a substring. The highest k where p remains a substring is our answer.
By following this approach, we can maximize the number of characters erased from s while ensuring p is still visible as a continuous phrase.
Let's understand with an example:
Maximum Number of Removable Characters Example:
Let's do a concise dry run of the example using the linear search approach to check if p is still a substring after removing the first k indices from removable.
Given Inputs:
- s = "abcbddddd"
- p = "abcd"
- removable = [3,2,1,4,5,6]
Step-by-step Dry Run:
We start with k = 0 and gradually remove characters at indices from removable until p is no longer a substring.
Checking for k = 0:
- s = "abcbddddd" (unchanged)
- p = "abcd" is a substring
Checking for k = 1 (Remove index 3 → 'b')
- s = "abc#ddddd" (Marked removed character with '#')
- p = "abcd" is still a substring
Checking for k = 2 (Remove indices [3,2] → 'b', 'c')
- s = "ab##ddddd"
- p = "abcd" is not a substring
- We lost the full sequence "abcd" as a continuous block.
Final Answer:
The maximum k for which p remains a substring is k = 1.
Steps to Implement the Solution:
- Define a helper function (isPossible)
- Take input parameters: s, p, removable, and k.
- Mark the first k indices from removable in s with a special character (e.g., #) to simulate removal.
- Check if
premains a subsequence of s after removal - Use a pointer j to track characters in p.
- Iterate through s, skipping removed characters.
- If s[i] matches p[j], increment j.
- If j reaches the length of p, return true (p is still a subsequence).
- If the loop completes without matching all of p, return false.
- Define the main function (maximumRemovals)
- Initialize low = 0 and high = removable.length() to define the search space.
- Use a variable k = 0 to store the maximum removable count.
- Perform a linear search from 0 to high
- Iterate i from low to high.
- Call isPossible(s, p, removable, i) to check feasibility.
- If true, update k = i (maximize removals while keeping p a subsequence).
- Return the maximum k value found
- The final value of k is the answer.
Maximum Number of Removable Characters leetcode solution
Maximum Number of Removable Characters / Code Implementation
1. Maximum Number of Removable Characters solution in c++ Try on Compiler
class Solution {
// Function to check if p is still a subsequence of s after removing k characters
bool isPossible(string s, string &p, vector<int> &removable, int k)
{
// Mark the first k removable indices with '#'
for(int i = 0; i < k; i++)
{
s[removable[i]] = '#';
}
// Pointer j to track characters of p in s
int j = 0;
// Iterate through s to check if p still exists as a subsequence
for(int i = 0; i < s.length(); i++)
{
// If a character matches the current character of p, move the pointer in p
if(s[i] == p[j])
{
j++;
}
// If all characters of p are found in order, return true
if(j == p.length())
return true;
}
// If p is not found as a subsequence, return false
return false;
}
public:
// Function to find the maximum number of removable characters
int maximumRemovals(string s, string p, vector<int>& removable) {
int low = 0;
int high = removable.size();
// Variable to store the maximum k value
int k = 0;
// Perform linear search from 0 to high
for(int i = low; i <= high; i++)
{
// If p is still a subsequence after removing i characters, update k
if(isPossible(s, p, removable, i))
{
k = i;
}
}
// Return the maximum k value found
return k;
}
};
2. Maximum Number of Removable Characters solution in Java Try on Compiler
class Solution {
// Function to check if p is still a subsequence of s after removing k characters
private boolean isPossible(String s, String p, int[] removable, int k) {
// Convert s to a mutable character array
char[] sArray = s.toCharArray();
// Mark the first k removable indices with '#'
for (int i = 0; i < k; i++) {
sArray[removable[i]] = '#';
}
// Pointer j to track characters of p in s
int j = 0;
// Iterate through sArray to check if p still exists as a subsequence
for (char ch : sArray) {
// If a character matches the current character of p, move the pointer in p
if (j < p.length() && ch == p.charAt(j)) {
j++;
}
// If all characters of p are found in order, return true
if (j == p.length()) {
return true;
}
}
// If p is not found as a subsequence, return false
return false;
}
// Function to find the maximum number of removable characters
public int maximumRemovals(String s, String p, int[] removable) {
int low = 0;
int high = removable.length;
// Variable to store the maximum k value
int k = 0;
// Perform linear search from 0 to high
for (int i = low; i <= high; i++) {
// If p is still a subsequence after removing i characters, update k
if (isPossible(s, p, removable, i)) {
k = i;
}
}
// Return the maximum k value found
return k;
}
}
3. Maximum Number of Removable Characters solution in Python Try on Compiler
class Solution:
# Function to check if p is still a subsequence of s after removing k characters
def isPossible(self, s, p, removable, k):
# Convert s into a list to allow modification
s_list = list(s)
# Mark the first k removable indices with '#'
for i in range(k):
s_list[removable[i]] = '#'
# Pointer j to track characters of p in s
j = 0
# Iterate through s_list to check if p still exists as a subsequence
for ch in s_list:
# If a character matches the current character of p, move the pointer in p
if j < len(p) and ch == p[j]:
j += 1
# If all characters of p are found in order, return True
if j == len(p):
return True
# If p is not found as a subsequence, return False
return False
# Function to find the maximum number of removable characters
def maximumRemovals(self, s, p, removable):
low = 0
high = len(removable)
# Variable to store the maximum k value
k = 0
# Perform linear search from 0 to high
for i in range(low, high + 1):
# If p is still a subsequence after removing i characters, update k
if self.isPossible(s, p, removable, i):
k = i
# Return the maximum k value found
return k
4. Maximum Number of Removable Characters solution in Javascript Try on Compiler
/**
* @param {string} s
* @param {string} p
* @param {number[]} removable
* @return {number}
*/
var isPossible = function (s, p, removable, k) {
// Convert s into an array to allow modification
let sArray = s.split("");
// Mark the first k removable indices with '#'
for (let i = 0; i < k; i++) {
sArray[removable[i]] = "#";
}
// Pointer j to track characters of p in s
let j = 0;
// Iterate through sArray to check if p still exists as a subsequence
for (let ch of sArray) {
// If a character matches the current character of p, move the pointer in p
if (j < p.length && ch === p[j]) {
j++;
}
// If all characters of p are found in order, return true
if (j === p.length) {
return true;
}
}
// If p is not found as a subsequence, return false
return false;
}
var maximumRemovals = function (s, p, removable) {
let low = 0;
let high = removable.length;
// Variable to store the maximum k value
let k = 0;
// Perform linear search from 0 to high
for (let i = low; i <= high; i++) {
// If p is still a subsequence after removing i characters, update k
if (isPossible(s, p, removable, i)) {
k = i;
}
}
// Return the maximum k value found
return k;
};Complexity Analysis of Maximum Number of Removable Characters(brute force):
Time Complexity: O(r * n)
The given approach consists of two main functions:
- isPossible(s, p, removable, k) - Checks if p is still a subsequence after removing the first k indices from removable.
- maximumRemovals(s, p, removable) - Iterates through possible values of k from 0 to removable.length and uses isPossible() to find the maximum valid k.
Analyzing isPossible(s, p, removable, k)
- Marking k characters as # in s:
- This takes O(k) time since we iterate over the first k indices in removable and mark them.
- Checking if p is still a subsequence in the modified s:
- We iterate over s (O(n), where n is the length of s), using a two-pointer technique to check for p (O(m), where m is the length of p).
- The worst-case complexity here is O(n) since every character of s is checked.
Thus, isPossible() has a time complexity of O(k + n) ≈ O(n) (as k ≤ n in the worst case).
Analyzing maximumRemovals(s, p, removable)
- We iterate from k = 0 to removable.length, calling isPossible() for each k.
- The loop runs O(r + 1) times (where r = removable.length), and in each iteration, we call isPossible(), which takes O(n).
- This results in an overall complexity of O(r * n) in the worst case.
Space Complexity: O(n)
- Auxiliary Space Complexity: O(1)
The solution uses only a few integer variables (low, high, k, i, j), which take O(1) space.
Therefore, the auxiliary space complexity is O(1). - Total Space Complexity: O(n)
The input string s takes O(n) space, where n is the length of s. The removable[] array takes O(r) space, where r is the number of removable indices.
Since r ≤ n, the total space complexity remains O(n).
Will Brute Force Work Against the Given Constraints?
For the given solution, the time complexity is O(r * n), where:
- n is the length of s (with an upper limit of 10⁵).
- r is the length of removable (with an upper limit of n - 1).
In the worst case, r could be close to 10⁵, leading to a time complexity of O(10⁵ * 10⁵) = 10¹⁰ operations.
This time complexity can become inefficient when both n and r are large, particularly when removable.length is close to s.length. In such cases, the algorithm may perform up to 10¹⁰ operations, making it impractical for large inputs due to exceeding typical computational limits.
In competitive programming environments, the typical time complexity limit is around 10⁶ operations per test case. Therefore, for inputs where n and r are large, this time complexity could lead to inefficient execution.
How to optimize it?
In the previous approach, we checked every possible value of k (from 0 to removable.length()) and verified if p was still a subsequence of s after removing the first k indices. This resulted in O(n * removable.length()) time complexity, which was too slow and caused TLE (Time Limit Exceeded).
Now, let’s think about improving this.
The main issue was that we checked every possible value of k, which took too much time.
Can we make this part faster?
Yes! Here’s the hint:
We are searching for the maximum k such that p remains a subsequence of s after removing the first k indices. We know this maximum k lies between 0 (no removals) and removable.length() (all removals).
Now that we know the two endpoints, 0 and removable.length(), let's make a few observations:
- The data structure is sorted:
The range of possible values for k is naturally sorted from 0 to removable.length(). - The search space is monotonic:
- If a certain value k allows p to remain a subsequence, then any smaller k will also work.
- If a certain k does not allow p to remain a subsequence, then any larger k will also fail.
- For example, consider s = "abcacb", p = "ab", removable = [3,1,0]:
The algorithm successfully keeps p as a subsequence when removing k = 1, 2.
However, when attempting k = 3, p is no longer a subsequence.
This demonstrates the monotonic property of the problem.
- The middle element helps minimize or maximize the search space:
If we take the middle value of the current range (mid = (low + high) / 2) and check if it works (i.e., can we remove mid characters while keeping p as a subsequence), we can narrow the search space:
If it works, we move to the right half to try a larger k.
If it doesn’t work, we move to the left half to try a smaller k.
If we plot a graph with the range of k values on the x-axis and whether p remains a subsequence (1 for success, 0 for failure) on the y-axis, we observe the following:
- Before reaching the maximum valid k (maxK), we can successfully keep p as a subsequence.
- Once we go beyond maxK, we can no longer keep p as a subsequence.
This showcases the monotonic nature of the problem.
With these points in mind, it's clear that instead of linearly checking all possible values of k from 0 to removable.length(), we can take the middle value and continually reduce the search space.
Does this approach remind you of something you've seen before?
Yes, we are applying binary search here. By leveraging the sorted and monotonic properties of the removable indices, we efficiently narrow down the search space to find the maximum k instead of checking each value linearly.
Maximum Number of Removable Characters Binary Search Algorithm:
Binary search can help us quickly find the maximum k such that p remains a subsequence of s after removing the first k indices.
We can simply use binary search to determine the largest k that keeps p as a subsequence.
- Start with binary search:
- Initialize low = 0 and high = removable.length().
- The middle value mid = (low + high) / 2 represents the number of characters we attempt to remove.
- Check if removing mid indices keeps p as a subsequence:
- If p is still a subsequence after removing mid characters, we store mid as a potential answer and search in the right half for a larger valid value.
- Otherwise, we search in the left half to find a smaller valid value.
- Continue binary search while low <= high:
- At each step, we cut the search space in half, making the solution much faster.
- Once the condition breaks, the stored answer is returned as the maximum k that allows p to remain a subsequence.
By using binary search, we significantly reduce the number of checks, making the solution much more efficient and avoiding TLE issues.
Let us understand this with a video.
maximum-number-of-removable-characters-optimal-approach-animation
Let's understand with an example:
Maximum Number of Removable Characters Example:
Given Input:
s = "abcbddddd"
p = "abcd"
removable = [3,2,1,4,5,6]
Step 1: Initialize Binary Search
- low = 0, high = 6 (length of removable)
- Result (maxk) = 0
Step 2: Perform Binary SearchIteration 1:
- mid = (0 + 6) / 2 = 3
- Remove first 3 indices: [3,2,1]
- Modified s = "a###ddddd"
- p = "abcd" is no longer a subsequence
- Move left → high = 2
Iteration 2:
- mid = (0 + 2) / 2 = 1
- Remove first 1 indices: [3]
- Modified s = "abc#ddddd"
- p = "abcd" is still a subsequence
- Move right → low = 2, result = 1
Iteration 3:
- mid = (2 + 2) / 2 = 2
- Remove first 2 indices: [3,2]
- Modified s = "ab##ddddd"
- p = "abcd" is no longer a subsequence
- Move left → high = 1
Step 3: Termination
- low > high, binary search ends.
- Final answer: max k = 4
Output: 1
How to code it up:
- Define a function (isPossible) to check subsequence validity
Temporarily mark the first k indices in s (from removable) as removed.
Iterate through s to check if p remains a subsequence.
Return true if p is still a subsequence, otherwise return false. - Initialize binary search variables
Set low = 0 and high = removable.length to define the search space.
Initialize k = 0 to store the maximum removable count. - Perform binary search on k
Compute mid = (low + high) / 2 as the number of characters to remove.
Use isPossible(s, p, removable, mid) to check if p is still a subsequence:
If true, update k = mid and search for a higher value (low = mid + 1).
If false, reduce the search space (high = mid - 1).
Continue until low > high. - Return the maximum k found
The final value of k represents the maximum number of removable characters while ensuring p remains a subsequence.
Maximum Number of Removable Characters leetcode solution
Maximum Number of Removable Characters solution / Code Implementation
1. Maximum Number of Removable Characters solution in c++ Try on Compiler
class Solution {
// Function to check if p is still a subsequence of s after removing k characters
bool isPossible(string s, string &p, vector<int> &removable, int k)
{
// Mark the first k removable indices with '#'
for(int i = 0; i < k; i++)
{
s[removable[i]] = '#';
}
// Pointer j to track characters of p in s
int j = 0;
// Iterate through s to check if p still exists as a subsequence
for(int i = 0; i < s.length(); i++)
{
// If a character matches the current character of p, move the pointer in p
if(s[i] == p[j])
{
j++;
}
// If all characters of p are found in order, return true
if(j == p.length())
return true;
}
// If p is not found as a subsequence, return false
return false;
}
public:
// Function to find the maximum number of removable characters using binary search
int maximumRemovals(string s, string p, vector<int>& removable) {
// Initialize binary search range
int low = 0;
int high = removable.size();
// Variable to store the maximum k value
int k = 0;
// Perform binary search
while(low <= high)
{
// Find the middle index
int mid = (low + high) / 2;
// If p is still a subsequence after removing mid characters, update k and move right
if(isPossible(s, p, removable, mid))
{
k = mid;
low = mid + 1;
}
// Otherwise, move left to search for a smaller valid k
else
{
high = mid - 1;
}
}
// Return the maximum k value found
return k;
}
};
2. Maximum Number of Removable Characters solution in Java Try on Compiler
class Solution {
// Function to check if p is still a subsequence of s after removing k characters
private boolean isPossible(String s, String p, int[] removable, int k) {
char[] sArray = s.toCharArray();
// Mark the first k removable indices with '#'
for (int i = 0; i < k; i++) {
sArray[removable[i]] = '#';
}
// Pointer j to track characters of p in s
int j = 0;
// Iterate through s to check if p still exists as a subsequence
for (char c : sArray) {
if (c == p.charAt(j)) {
j++;
}
// If all characters of p are found in order, return true
if (j == p.length()) {
return true;
}
}
// If p is not found as a subsequence, return false
return false;
}
// Function to find the maximum number of removable characters using binary search
public int maximumRemovals(String s, String p, int[] removable) {
int low = 0;
int high = removable.length;
int k = 0;
// Perform binary search
while (low <= high) {
int mid = (low + high) / 2;
// If p is still a subsequence after removing mid characters, update k and move right
if (isPossible(s, p, removable, mid)) {
k = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
// Return the maximum k value found
return k;
}
}
3. Maximum Number of Removable Characters solution in Python Try on Compiler
class Solution:
# Function to check if p is still a subsequence of s after removing k characters
def isPossible(self, s, p, removable, k):
s_list = list(s)
# Mark the first k removable indices with '#'
for i in range(k):
s_list[removable[i]] = '#'
# Pointer j to track characters of p in s
j = 0
# Iterate through s to check if p still exists as a subsequence
for c in s_list:
if c == p[j]:
j += 1
# If all characters of p are found in order, return True
if j == len(p):
return True
# If p is not found as a subsequence, return False
return False
# Function to find the maximum number of removable characters using binary search
def maximumRemovals(self, s, p, removable):
low, high = 0, len(removable)
k = 0
# Perform binary search
while low <= high:
mid = (low + high) // 2
# If p is still a subsequence after removing mid characters, update k and move right
if self.isPossible(s, p, removable, mid):
k = mid
low = mid + 1
else:
high = mid - 1
# Return the maximum k value found
return k
4. Maximum Number of Removable Characters solution in Javascript Try on Compiler
/**
* @param {string} s
* @param {string} p
* @param {number[]} removable
* @return {number}
*/
var isPossible = function (s, p, removable, k) {
// Convert s into an array to allow modification
let sArray = s.split("");
// Mark the first k removable indices with '#'
for (let i = 0; i < k; i++) {
sArray[removable[i]] = "#";
}
// Pointer j to track characters of p in s
let j = 0;
// Iterate through sArray to check if p still exists as a subsequence
for (let ch of sArray) {
// If a character matches the current character of p, move the pointer in p
if (j < p.length && ch === p[j]) {
j++;
}
// If all characters of p are found in order, return true
if (j === p.length) {
return true;
}
}
// If p is not found as a subsequence, return false
return false;
}
var maximumRemovals = function (s, p, removable) {
let low = 0, high = removable.length, k = 0;
// Perform binary search
while (low <= high) {
let mid = Math.floor((low + high) / 2);
// If p is still a subsequence after removing mid characters, update k and move right
if (isPossible(s, p, removable, mid)) {
k = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
// Return the maximum k value found
return k;
};Complexity Analysis of Maximum Number of Removable Characters (binary search):
Time Complexity : O(m log n)
The algorithm consists of two main components:
- Binary Search on k (Maximum Removable Count)
- Checking if p is a Subsequence of s (Helper Function isPossible)
1. Binary Search on k
- We perform a binary search on k, which is the number of characters we can remove.
- The search range is [0, removable.length], which means we perform at most O(log n) iterations, where n = removable.length.
2. Checking if p is a Subsequence (isPossible Function)
- Inside each binary search iteration, we call the isPossible function to check if p remains a subsequence after removing k characters.
- This function iterates through s once to check for the subsequence.
- The worst-case scenario occurs when we iterate through the entire string s, which takes O(m) time, where m = s.length.
Overall Time Complexity
- Binary search takes O(log n) iterations.
- Each iteration calls isPossible, which runs in O(m) time.
- Therefore, the total complexity is O(m log n).
Space Complexity : O(n)
- Auxiliary Space Complexity: O(1)
The solution uses only a few integer variables (low, high, k, i, j), which take O(1) space.
Therefore, the auxiliary space complexity is O(1). - Total Space Complexity: O(n)
The input string s takes O(n) space, where n is the length of s. The removable[] array takes O(r) space, where r is the number of removable indices.
Since r ≤ n, the total space complexity remains O(n).
Similar Problems
When solving array problems on Leetcode, techniques like Two Pointers and Binary Search often come in handy for optimization. For instance, in the Split Array into Maximum Number of Subarrays problem, we may need to strategically partition an array to maximize subarrays while maintaining certain constraints. Similarly, in Split Array Largest Sum, Binary Search on the answer helps find the optimal way to divide an array while minimizing the largest sum among subarrays. On the other hand, string-related problems like Maximum Occurring Character require efficient frequency counting and traversal to determine the most frequent character. Another challenging problem is Minimize the Maximum Difference Between Adjacent Elements in an Array, where a careful approach is needed to balance differences optimally. These problems often demand a mix of greedy techniques, dynamic programming, or binary search to arrive at efficient solutions.
Now we have successfully tackled this problem, let's try these similar problems.
You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.
You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can be allocated candies from only one pile of candies and some piles of candies may go unused.
Return the maximum number of candies each child can get.