Check If Word Is Valid After Substitutions — Solution
Check If Word Is Valid After Substitutions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Check If Word Is Valid After Substitutions is a medium coding problem on strings and stack, asked in Amazon, Google and Nutanix interviews.
- Difficulty: Medium
- Topics: Strings, Stack
- Asked at: Amazon, Google, Nutanix
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string is valid if it can be built from the empty string by repeatedly inserting "abc" at any position.
Given a string s, return true if it is valid.
Example 1
Input: s = "aabcbc"
Output: true
Explanation: Insert "abc" into "abc" after the first a.
Example 2
Input: s = "abcabcababcc"
Output: true
Example 3
Input: s = "abccba"
Output: false
Constraints
1 <= s.length <= 40s consists of the letters 'a', 'b' and 'c'.
Hints for Check If Word Is Valid After Substitutions
Hint 1
Every insertion places
abccontiguously, so the string always contains anabcyou can delete.Hint 2
Push characters on a stack; when you see a
c, the two items below it must beathenb.Hint 3
If that check ever fails, or anything is left on the stack at the end, the string is invalid.
How to solve Check If Word Is Valid After Substitutions
Every insertion places abc contiguously, so a valid string always contains an abc to delete. Push characters; on c, the top two must be a, b.
Approach
- For
aorb, push. - For
c, pop two and require them to bebthena; fail otherwise. - Return whether the stack is empty.
Why it works
Reversing the insertion process by repeatedly deleting abc works in any order, and the stack finds the leftmost-completed one each time.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- A length not divisible by 3 can be rejected immediately.
Reference solution
Python
def isValid(s: str) -> bool:
stack = []
for ch in s:
if ch == "c":
if len(stack) < 2:
return False
b = stack.pop()
a = stack.pop()
if a != "a" or b != "b":
return False
else:
stack.append(ch)
return len(stack) == 0Java
public static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == 'c') {
if (stack.size() < 2) return false;
char b = stack.pop();
char a = stack.pop();
if (a != 'a' || b != 'b') return false;
} else {
stack.push(c);
}
}
return stack.isEmpty();
}C++
bool isValid(string s) {
vector<char> stack;
for (char c : s) {
if (c == 'c') {
if (stack.size() < 2) return false;
char b = stack.back();
stack.pop_back();
char a = stack.back();
stack.pop_back();
if (a != 'a' || b != 'b') return false;
} else {
stack.push_back(c);
}
}
return stack.empty();
}JavaScript
var isValid = function(s) {
const stack = [];
for (let i = 0; i < s.length; i++) {
const c = s.charAt(i);
if (c === "c") {
if (stack.length < 2) return false;
const b = stack.pop();
const a = stack.pop();
if (a !== "a" || b !== "b") return false;
} else {
stack.push(c);
}
}
return stack.length === 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Stack Data Structure