Problem#
Given a string s
, determine if it is valid .
A string s
is valid if, starting with an empty string t = ""
, you can transform t
into s
after performing the following operation any number of times :
Insert string "abc"
into any position in t
. More formally, t
becomes tleft + "abc" + tright
, where t == tleft + tright
. Note that tleft
and tright
may be empty .
Return true
if s
is avalid string, otherwise, return false
.
Examples#
Example 1#
1
2
3
4
5
Input: s = "aabcbc"
Output: true
Explanation:
"" -> "_abc_ " -> "a _abc_ bc"
Thus, "aabcbc" is valid.
Example 2#
1
2
3
4
5
Input: s = "abcabcababcc"
Output: true
Explanation:
"" -> "_abc_ " -> "abc _abc_ " -> "abcabc _abc_ " -> "abcabcab _abc_ c"
Thus, "abcabcababcc" is valid.
Example 3#
1
2
3
Input: s = "abccba"
Output: false
Explanation: It is impossible to get "abccba" using the operation.
Constraints#
1 <= s.length <= 2 * 10^4
s
consists of letters 'a'
, 'b'
, and 'c'
Solution#
Method 1 – Stack Simulation#
Intuition#
Since only the substring “abc” can be inserted, any valid string must be reducible to the empty string by repeatedly removing “abc” substrings. We can simulate this process using a stack.
Reasoning#
By pushing characters onto a stack and checking if the top three characters form “abc”, we can remove them whenever they appear. If the stack is empty at the end, the string is valid.
Approach#
Initialize an empty stack.
Iterate through each character in the string:
Push the character onto the stack.
If the top three characters on the stack are ‘a’, ‘b’, ‘c’ (in order), pop them.
After processing all characters, return true if the stack is empty, otherwise false.
Edge cases:
Strings shorter than 3 are never valid.
Strings with leftover characters after all possible removals are invalid.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public :
bool isValid(string s) {
vector< char > stk;
for (char c : s) {
stk.push_back(c);
if (stk.size() >= 3 && stk[stk.size()- 3 ] == 'a' && stk[stk.size()- 2 ] == 'b' && stk[stk.size()- 1 ] == 'c' ) {
stk.pop_back(); stk.pop_back(); stk.pop_back();
}
}
return stk.empty();
}
};
1
2
3
4
5
6
7
8
9
10
11
func isValid (s string ) bool {
stk := []byte {}
for i := 0 ; i < len(s ); i ++ {
stk = append(stk , s [i ])
n := len(stk )
if n >= 3 && stk [n - 3 ] == 'a' && stk [n - 2 ] == 'b' && stk [n - 1 ] == 'c' {
stk = stk [:n - 3 ]
}
}
return len(stk ) == 0
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public boolean isValid (String s) {
StringBuilder stk = new StringBuilder();
for (char c : s.toCharArray ()) {
stk.append (c);
int n = stk.length ();
if (n >= 3 && stk.charAt (n- 3) == 'a' && stk.charAt (n- 2) == 'b' && stk.charAt (n- 1) == 'c' ) {
stk.setLength (n- 3);
}
}
return stk.length () == 0;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
fun isValid (s: String): Boolean {
val stk = StringBuilder()
for (c in s) {
stk.append(c)
val n = stk.length
if (n >= 3 && stk[n-3 ] == 'a' && stk[n-2 ] == 'b' && stk[n-1 ] == 'c' ) {
stk.setLength(n-3 )
}
}
return stk.isEmpty()
}
}
1
2
3
4
5
6
7
8
class Solution :
def is_valid (self, s: str) -> bool:
stk = []
for c in s:
stk. append(c)
if len(stk) >= 3 and stk[- 3 :] == ['a' , 'b' , 'c' ]:
stk. pop(); stk. pop(); stk. pop()
return not stk
1
2
3
4
5
6
7
8
9
10
11
12
13
impl Solution {
pub fn is_valid (s: String) -> bool {
let mut stk = Vec::new();
for c in s.chars() {
stk.push(c);
let n = stk.len();
if n >= 3 && stk[n- 3 ] == 'a' && stk[n- 2 ] == 'b' && stk[n- 1 ] == 'c' {
stk.truncate(n- 3 );
}
}
stk.is_empty()
}
}
Complexity#
⏰ Time complexity: O(n)
, as each character is pushed and popped at most once.
🧺 Space complexity: O(n)
, as the stack can grow up to the length of the string.