C++-এ Check If Word Is Valid After Substitutions

ধরি আমাদের দেওয়া আছে স্ট্রিং "abc" ভ্যালিড। তাই যেকোনো ভ্যালিড স্ট্রিং V থেকে, আমরা V কে দুটি পিস X এবং Y-তে ভাগ করতে পারি যাতে X + Y, V-এর সমান হয়। (X বা Y খালি হতে পারে)। তখন, X + "abc" + Y ও ভ্যালিড হবে। উদাহরণস্বরূপ S = "abc", তবে ভ্যালিড স্ট্রিং এর উদাহরণ: "abc", "aabcbc", "abcabc", "abcabcababcc"। আর ইনভ্যালিড স্ট্রিং এর উদাহরণ: "abccba", "ab", "cababc", "bac"। আমাদের চেক করতে হবে true রিটার্ন করব যদি এবং কেবল যদি দেওয়া স্ট্রিং S ভ্যালিড হয়।

ইনপুট যদি "abcabcababcc" হয়, তবে সেটা ভ্যালিড, তাই আউটপুট হবে true।

এটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:

একটি স্ট্যাক st ডিফাইন করুন
i = 0 থেকে S.size() - 1 পর্যন্ত লুপ চালান
- যদি st খালি হয় বা S[i] 'c' না হয়, তবে S[i] স্টকে পাশ করুন
- অন্যথায়
  - c স্টকে ইনসার্ট করুন
  - যখন পর্যন্ত st.size() >= 3
    - c := st.top() এবং st থেকে টপ এলিমেন্ট পপ করুন
    - b := st.top() এবং st থেকে টপ এলিমেন্ট পপ করুন
    - a := st.top() এবং st থেকে টপ এলিমেন্ট পপ করুন
    - temp := temp কনক্যাটেনেট উইথ a
    - temp := temp কনক্যাটেনেট উইথ b
    - temp := temp কনক্যাটেনেট উইথ c
    - যদি temp "abc" হয়, তবে পরবর্তী ইটারেশন জন্য যান
    - অন্যথায়
      - a, b, c স্টকে পাশ করুন, এবং লুপ ব্রেক করুন
- st খালি হলে true রিটার্ন করুন, অন্যথায় false
নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বোঝার জন্য:

উদাহরণ
```
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isValid(string S) {
        stack<char> st;
        for(int i = 0; i < S.size(); i++) {
            if(st.empty() || S[i] != 'c') {
                st.push(S[i]);
            } else {
                st.push('c');
                while(st.size() >= 3) {
                    char c = st.top(); st.pop();
                    char b = st.top(); st.pop();
                    char a = st.top(); st.pop();
                    string temp = "";
                    temp += a;
                    temp += b;
                    temp += c;
                    if(temp == "abc") {
                        continue;
                    } else {
                        st.push(a);
                        st.push(b);
                        st.push(c);
                        break;
                    }
                }
            }
        }
        return st.empty();
    }
};

int main() {
    Solution ob;
    cout << (ob.isValid("abcabcababcc"));
}
```
ইনপুট
```
"abcabcababcc"
```
আউটপুট
```
1
```