Lecture 159:-Check If Word Is Valid After Substitutions

The problem of checking if a given string is valid after applying certain substitutions can be solved using a stack. In this problem, you are given a string containing only the characters 'a', 'b', and 'c'. You can perform the following operation: choose any two adjacent characters and replace them with "c" if they are "ab" or "bc". The goal is to determine if the given string can be made valid after performing zero or more such operations.

Here's how you can approach this problem:

1. Iterate through the characters of the string.
2. For each character, if the stack is not empty and the top two characters of the stack are 'a' and 'b', pop the top two characters.
3. If the above step was not performed, push the current character onto the stack.
4. After iterating through all characters, if the stack is empty, the string is valid; otherwise, it is not.

Here's a C++ implementation to check if a given string is valid after substitutions:

cppCopy code

#include <iostream> #include <stack> bool isValidAfterSubstitutions(const std::string& s) { std::stack<char> charStack; for (char ch : s) { if (!charStack.empty() && charStack.top() == 'a' && ch == 'b') { charStack.pop(); } else if (!charStack.empty() && charStack.top() == 'b' && ch == 'c') { charStack.pop(); } else { charStack.push(ch); } } return charStack.empty(); } int main() { std::string input = "abcab"; bool isValid = isValidAfterSubstitutions(input); if (isValid) { std::cout << "The string is valid after substitutions." << std::endl; } else { std::cout << "The string is not valid after substitutions." << std::endl; } return 0; }

In this example, the isValidAfterSubstitutions function checks whether the given string is valid after applying the described substitutions. The main function demonstrates how to use this function for a specific input string.

For the input "abcab", the output will be "The string is valid after substitutions," as the string can be made valid by replacing the adjacent characters "ab" with "c".