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:
"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 a valid string, otherwise, return false.
Example 1:
Input: s = "aabcbc" Output: true Explanation: "" -> "abc" -> "aabcbc" Thus, "aabcbc" is valid.
Example 2:
Input: s = "abcabcababcc" Output: true Explanation: "" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc" Thus, "abcabcababcc" is valid.
Example 3:
Input: s = "abccba" Output: false Explanation: It is impossible to get "abccba" using the operation.
Constraints:
1 <= s.length <= 2 * 104s consists of letters 'a', 'b', and 'c'This approach leverages a stack data structure to validate the string. The main idea is to iterate over each character in the string and utilize the stack to check for the sequence 'abc'. When 'abc' is encountered, it is removed from the stack, simulating the reverse operation of building the string with 'abc'. If the stack is empty after processing all characters, the string is valid.
The function uses a stack to keep track of characters as we iterate through the string. Whenever the last three characters in the stack form the sequence 'abc', they are removed from the stack. The function returns true if the stack is empty at the end, indicating that the string can be completely reduced by removing 'abc' sequences.
Java
Time Complexity: O(n) where n is the length of the string because we process each character once.
Space Complexity: O(n) in the worst case where the stack might store all characters if no 'abc' sequence is found.
This approach involves iteratively searching for and replacing occurrences of the substring 'abc' in the string until no more are found. If the final string is empty, it suggests all parts of the string have been validly constructed using 'abc'.
This JavaScript solution iteratively replaces occurrences of 'abc' in the string. By continually replacing 'abc' with an empty string until no more replacements can be made, it checks if the resulting string is empty. An empty result means the original string was valid.
C#
Time Complexity: O(n^2) because each replacement operation may scan the entire string.
Space Complexity: O(n) for storing substrings temporarily during operations.
| Approach | Complexity |
|---|---|
| Stack-Based Approach for Validation | Time Complexity: O(n) where n is the length of the string because we process each character once. |
| String Replacement Iteration | Time Complexity: O(n^2) because each replacement operation may scan the entire string. |
Google Coding Interview Question - Validate Stack Sequences (LeetCode) • AlgosWithMichael • 10,131 views views
Watch 9 more video solutions →Practice Check If Word Is Valid After Substitutions with our built-in code editor and test cases.
Practice on FleetCode