मान लीजिए हमारे पास '(', ')' और लोअरकेस अंग्रेजी वर्णों की एक स्ट्रिंग s है। हमें न्यूनतम संख्या में पैरेंथेसिस ( '(' या ')', किसी भी स्थिति में ) को हटाना होगा ताकि परिणामी पैरेंथेसिस स्ट्रिंग वैध हो और कोई भी वैध स्ट्रिंग लौटाएं। एक पैरेंथेसिस स्ट्रिंग तब वैध होती है जब ये सभी मानदंड पूरे होते हैं:
यह खाली स्ट्रिंग है, केवल लोअरकेस वर्ण रखता है, या
इसे AB के रूप में लिखा जा सकता है (A को B के साथ जोड़कर), जहां A और B वैध स्ट्रिंग्स हैं, या
इसे (A) के रूप में लिखा जा सकता है, जहां A एक वैध स्ट्रिंग है।
इसलिए यदि इनपुट "a)b(c)d" जैसा है, तो आउटपुट "ab(c)d" होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
एक स्टैक st परिभाषित करें
i को 0 से s के आकार तक के लिए
यदि s[i] = '(', तो i को st में सम्मिलित करें
अन्यथा जब s[i] ')' हो, तो
यदि स्टैक खाली नहीं है, तो स्टैक से पॉप करें, अन्यथा s[i] = '*'
जब तक st खाली नहीं है,
s[स्टैक का शीर्ष तत्व] = '*'
स्टैक से पॉप करें
ans := खाली स्ट्रिंग
i को 0 से s के आकार - 1 तक के लिए
यदि s[i] '*' नहीं है, तो ans := ans + s[i]
ans लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string minRemoveToMakeValid(string s) {
stack <int> st;
for(int i = 0; i < s.size(); i++) {
if(s[i] == '(') st.push(i);
else if(s[i] == ')') {
if(!st.empty()) st.pop();
else s[i] = '*';
}
}
while(!st.empty()) {
s[st.top()] = '*';
st.pop();
}
string ans = "";
for(int i = 0; i < s.size(); i++) {
if(s[i] != '*') ans += s[i];
}
return ans;
}
};
int main() {
Solution ob;
cout << (ob.minRemoveToMakeValid("a)b(c)d"));
}
इनपुट
"a)b(c)d"
आउटपुट
ab(c)d
