1898. Maximum Number of Removable Characters LeetCode Solution
In this guide, you will get 1898. Maximum Number of Removable Characters LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Removable Characters problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Number of Removable Characters
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.
Example 1:
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”.
Example 3:
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 <= 105
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.
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(n)
1898. Maximum Number of Removable Characters LeetCode Solution in C++
class Solution {
public:
int maximumRemovals(string s, string p, vector<int>& removable) {
int l = 0;
int r = removable.size() + 1;
while (l < r) {
const int m = (l + r) / 2;
const string removed = remove(s, removable, m);
if (isSubsequence(p, removed))
l = m + 1;
else
r = m;
}
return l - 1;
}
private:
string remove(const string& s, const vector<int>& removable, int k) {
string removed(s);
for (int i = 0; i < k; ++i)
removed[removable[i]] = '*';
return removed;
}
bool isSubsequence(const string& p, const string& s) {
int i = 0; // p's index
for (int j = 0; j < s.length(); ++j)
if (p[i] == s[j])
if (++i == p.length())
return true;
return false;
}
}; /* code provided by PROGIEZ */
1898. Maximum Number of Removable Characters LeetCode Solution in Java
class Solution {
public int maximumRemovals(String s, String p, int[] removable) {
int l = 0;
int r = removable.length + 1;
while (l < r) {
final int m = (l + r) / 2;
final String removed = remove(s, removable, m);
if (isSubsequence(p, removed))
l = m + 1;
else
r = m;
}
return l - 1;
}
private String remove(final String s, int[] removable, int k) {
StringBuilder sb = new StringBuilder(s);
for (int i = 0; i < k; ++i)
sb.setCharAt(removable[i], '*');
return sb.toString();
}
private boolean isSubsequence(final String p, final String s) {
int i = 0; // p's index
for (int j = 0; j < s.length(); ++j)
if (p.charAt(i) == s.charAt(j))
if (++i == p.length())
return true;
return false;
}
} // code provided by PROGIEZ
1898. Maximum Number of Removable Characters LeetCode Solution in Python
class Solution:
def maximumRemovals(self, s: str, p: str, removable: list[int]) -> int:
l = 0
r = len(removable) + 1
def remove(k: int) -> str:
removed = [c for c in s]
for i in range(k):
removed[removable[i]] = '*'
return ''.join(removed)
def isSubsequence(p: str, s: str) -> bool:
i = 0
for j, c in enumerate(s):
if p[i] == s[j]:
i += 1
if i == len(p):
return True
return False
while l < r:
m = (l + r) // 2
removed = remove(m)
if isSubsequence(p, removed):
l = m + 1
else:
r = m
return l - 1 # code by PROGIEZ
