Skip to content

Commit d263209

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1898. Maximum Number of Removable Characters
1 parent 45ece9f commit d263209

File tree

6 files changed

+248
-63
lines changed

6 files changed

+248
-63
lines changed

‎solution/1800-1899/1898.Maximum Number of Removable Characters/README.md

Lines changed: 86 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -72,24 +72,23 @@
7272
```python
7373
class Solution:
7474
def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
75-
def isSubsequence(mid):
76-
m, n = len(s), len(p)
77-
i = j = 0
78-
ids = {e for e in removable[:mid]}
75+
def check(mid):
76+
m, n, i, j = len(s), len(p), 0, 0
77+
ids = set(removable[:mid])
7978
while i < m and j < n:
8079
if i not in ids and s[i] == p[j]:
8180
j += 1
8281
i += 1
8382
return j == n
8483

85-
low, high = 0, len(removable)
86-
while low < high:
87-
mid = (low + high + 1) >> 1
88-
if isSubsequence(mid):
89-
low = mid
84+
left, right = 0, len(removable)
85+
while left < right:
86+
mid = (left + right + 1) >> 1
87+
if check(mid):
88+
left = mid
9089
else:
91-
high = mid - 1
92-
return low
90+
right = mid - 1
91+
return left
9392
```
9493

9594
### **Java**
@@ -99,21 +98,20 @@ class Solution:
9998
```java
10099
class Solution {
101100
public int maximumRemovals(String s, String p, int[] removable) {
102-
int low = 0, high = removable.length;
103-
while (low < high) {
104-
int mid = (low + high + 1) >> 1;
105-
if (isSubsequence(s, p, removable, mid)) {
106-
low = mid;
101+
int left = 0, right = removable.length;
102+
while (left < right) {
103+
int mid = (left + right + 1) >> 1;
104+
if (check(s, p, removable, mid)) {
105+
left = mid;
107106
} else {
108-
high = mid - 1;
107+
right = mid - 1;
109108
}
110109
}
111-
return low;
110+
return left;
112111
}
113112

114-
private boolean isSubsequence(String s, String p, int[] removable, int mid) {
115-
int m = s.length(), n = p.length();
116-
int i = 0, j = 0;
113+
private boolean check(String s, String p, int[] removable, int mid) {
114+
int m = s.length(), n = p.length(), i = 0, j = 0;
117115
Set<Integer> ids = new HashSet<>();
118116
for (int k = 0; k < mid; ++k) {
119117
ids.add(removable[k]);
@@ -158,6 +156,73 @@ function isSub(str: string, sub: string, idxes: Set<number>): boolean {
158156
}
159157
```
160158

159+
### **C++**
160+
161+
```cpp
162+
class Solution {
163+
public:
164+
int maximumRemovals(string s, string p, vector<int>& removable) {
165+
int left = 0, right = removable.size();
166+
while (left < right) {
167+
int mid = left + right + 1 >> 1;
168+
if (check(s, p, removable, mid)) {
169+
left = mid;
170+
} else {
171+
right = mid - 1;
172+
}
173+
}
174+
return left;
175+
}
176+
177+
bool check(string s, string p, vector<int>& removable, int mid) {
178+
int m = s.size(), n = p.size(), i = 0, j = 0;
179+
unordered_set<int> ids;
180+
for (int k = 0; k < mid; ++k) {
181+
ids.insert(removable[k]);
182+
}
183+
while (i < m && j < n) {
184+
if (ids.count(i) == 0 && s[i] == p[j]) {
185+
++j;
186+
}
187+
++i;
188+
}
189+
return j == n;
190+
}
191+
};
192+
```
193+
194+
### **Go**
195+
196+
```go
197+
func maximumRemovals(s string, p string, removable []int) int {
198+
left, right := 0, len(removable)
199+
for left < right {
200+
mid := (left + right + 1) >> 1
201+
if check(s, p, removable, mid) {
202+
left = mid
203+
} else {
204+
right = mid - 1
205+
}
206+
}
207+
return left
208+
}
209+
210+
func check(s string, p string, removable []int, mid int) bool {
211+
m, n, i, j := len(s), len(p), 0, 0
212+
ids := make(map[int]bool)
213+
for k := 0; k < mid; k++ {
214+
ids[removable[k]] = true
215+
}
216+
for i < m && j < n {
217+
if !ids[i] && s[i] == p[j] {
218+
j++
219+
}
220+
i++
221+
}
222+
return j == n
223+
}
224+
```
225+
161226
### **...**
162227

163228
```

‎solution/1800-1899/1898.Maximum Number of Removable Characters/README_EN.md

Lines changed: 86 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -62,46 +62,44 @@ Hence, the maximum k is 2.
6262
```python
6363
class Solution:
6464
def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
65-
def isSubsequence(mid):
66-
m, n = len(s), len(p)
67-
i = j = 0
68-
ids = {e for e in removable[:mid]}
65+
def check(mid):
66+
m, n, i, j = len(s), len(p), 0, 0
67+
ids = set(removable[:mid])
6968
while i < m and j < n:
7069
if i not in ids and s[i] == p[j]:
7170
j += 1
7271
i += 1
7372
return j == n
7473

75-
low, high = 0, len(removable)
76-
while low < high:
77-
mid = (low + high + 1) >> 1
78-
if isSubsequence(mid):
79-
low = mid
74+
left, right = 0, len(removable)
75+
while left < right:
76+
mid = (left + right + 1) >> 1
77+
if check(mid):
78+
left = mid
8079
else:
81-
high = mid - 1
82-
return low
80+
right = mid - 1
81+
return left
8382
```
8483

8584
### **Java**
8685

8786
```java
8887
class Solution {
8988
public int maximumRemovals(String s, String p, int[] removable) {
90-
int low = 0, high = removable.length;
91-
while (low < high) {
92-
int mid = (low + high + 1) >> 1;
93-
if (isSubsequence(s, p, removable, mid)) {
94-
low = mid;
89+
int left = 0, right = removable.length;
90+
while (left < right) {
91+
int mid = (left + right + 1) >> 1;
92+
if (check(s, p, removable, mid)) {
93+
left = mid;
9594
} else {
96-
high = mid - 1;
95+
right = mid - 1;
9796
}
9897
}
99-
return low;
98+
return left;
10099
}
101100

102-
private boolean isSubsequence(String s, String p, int[] removable, int mid) {
103-
int m = s.length(), n = p.length();
104-
int i = 0, j = 0;
101+
private boolean check(String s, String p, int[] removable, int mid) {
102+
int m = s.length(), n = p.length(), i = 0, j = 0;
105103
Set<Integer> ids = new HashSet<>();
106104
for (int k = 0; k < mid; ++k) {
107105
ids.add(removable[k]);
@@ -146,6 +144,73 @@ function isSub(str: string, sub: string, idxes: Set<number>): boolean {
146144
}
147145
```
148146

147+
### **C++**
148+
149+
```cpp
150+
class Solution {
151+
public:
152+
int maximumRemovals(string s, string p, vector<int>& removable) {
153+
int left = 0, right = removable.size();
154+
while (left < right) {
155+
int mid = left + right + 1 >> 1;
156+
if (check(s, p, removable, mid)) {
157+
left = mid;
158+
} else {
159+
right = mid - 1;
160+
}
161+
}
162+
return left;
163+
}
164+
165+
bool check(string s, string p, vector<int>& removable, int mid) {
166+
int m = s.size(), n = p.size(), i = 0, j = 0;
167+
unordered_set<int> ids;
168+
for (int k = 0; k < mid; ++k) {
169+
ids.insert(removable[k]);
170+
}
171+
while (i < m && j < n) {
172+
if (ids.count(i) == 0 && s[i] == p[j]) {
173+
++j;
174+
}
175+
++i;
176+
}
177+
return j == n;
178+
}
179+
};
180+
```
181+
182+
### **Go**
183+
184+
```go
185+
func maximumRemovals(s string, p string, removable []int) int {
186+
left, right := 0, len(removable)
187+
for left < right {
188+
mid := (left + right + 1) >> 1
189+
if check(s, p, removable, mid) {
190+
left = mid
191+
} else {
192+
right = mid - 1
193+
}
194+
}
195+
return left
196+
}
197+
198+
func check(s string, p string, removable []int, mid int) bool {
199+
m, n, i, j := len(s), len(p), 0, 0
200+
ids := make(map[int]bool)
201+
for k := 0; k < mid; k++ {
202+
ids[removable[k]] = true
203+
}
204+
for i < m && j < n {
205+
if !ids[i] && s[i] == p[j] {
206+
j++
207+
}
208+
i++
209+
}
210+
return j == n
211+
}
212+
```
213+
149214
### **...**
150215

151216
```

‎solution/1800-1899/1898.Maximum Number of Removable Characters/Solution.cpp

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
class Solution {
2+
public:
3+
int maximumRemovals(string s, string p, vector<int>& removable) {
4+
int left = 0, right = removable.size();
5+
while (left < right) {
6+
int mid = left + right + 1 >> 1;
7+
if (check(s, p, removable, mid)) {
8+
left = mid;
9+
} else {
10+
right = mid - 1;
11+
}
12+
}
13+
return left;
14+
}
15+
16+
bool check(string s, string p, vector<int>& removable, int mid) {
17+
int m = s.size(), n = p.size(), i = 0, j = 0;
18+
unordered_set<int> ids;
19+
for (int k = 0; k < mid; ++k) {
20+
ids.insert(removable[k]);
21+
}
22+
while (i < m && j < n) {
23+
if (ids.count(i) == 0 && s[i] == p[j]) {
24+
++j;
25+
}
26+
++i;
27+
}
28+
return j == n;
29+
}
30+
};

‎solution/1800-1899/1898.Maximum Number of Removable Characters/Solution.go

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
func maximumRemovals(s string, p string, removable []int) int {
2+
left, right := 0, len(removable)
3+
for left < right {
4+
mid := (left + right + 1) >> 1
5+
if check(s, p, removable, mid) {
6+
left = mid
7+
} else {
8+
right = mid - 1
9+
}
10+
}
11+
return left
12+
}
13+
14+
func check(s string, p string, removable []int, mid int) bool {
15+
m, n, i, j := len(s), len(p), 0, 0
16+
ids := make(map[int]bool)
17+
for k := 0; k < mid; k++ {
18+
ids[removable[k]] = true
19+
}
20+
for i < m && j < n {
21+
if !ids[i] && s[i] == p[j] {
22+
j++
23+
}
24+
i++
25+
}
26+
return j == n
27+
}

‎solution/1800-1899/1898.Maximum Number of Removable Characters/Solution.java

Lines changed: 9 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,19 @@
11
class Solution {
22
public int maximumRemovals(String s, String p, int[] removable) {
3-
int low = 0, high = removable.length;
4-
while (low < high) {
5-
int mid = (low + high + 1) >> 1;
6-
if (isSubsequence(s, p, removable, mid)) {
7-
low = mid;
3+
int left = 0, right = removable.length;
4+
while (left < right) {
5+
int mid = (left + right + 1) >> 1;
6+
if (check(s, p, removable, mid)) {
7+
left = mid;
88
} else {
9-
high = mid - 1;
9+
right = mid - 1;
1010
}
1111
}
12-
return low;
12+
return left;
1313
}
1414

15-
private boolean isSubsequence(String s, String p, int[] removable, int mid) {
16-
int m = s.length(), n = p.length();
17-
int i = 0, j = 0;
15+
private boolean check(String s, String p, int[] removable, int mid) {
16+
int m = s.length(), n = p.length(), i = 0, j = 0;
1817
Set<Integer> ids = new HashSet<>();
1918
for (int k = 0; k < mid; ++k) {
2019
ids.add(removable[k]);

0 commit comments

Comments
 (0)