मान लीजिए हमारे पास लोअरकेस अक्षरों की एक स्ट्रिंग है और हमारे पास लागतों की एक सूची भी है जिसे costs कहा जाता है। स्ट्रिंग और सूची की लंबाई समान होती है। हम कैरेक्टर s[i] को costs[i] लागत पर हटा सकते हैं, और फिर दोनों s[i] और costs[i] हट जाते हैं। हमें सभी लगातार दोहराए जाने वाले कैरेक्टर्स को हटाने की न्यूनतम लागत ज्ञात करनी है।
उदाहरण के लिए, यदि इनपुट s = "xxyyx" और nums = [2, 3, 10, 4, 6] है, तो आउटपुट 6 होगा, क्योंकि हम s[0] और s[3] को कुल लागत 2 + 4 = 6 पर हटा सकते हैं।
समाधान दृष्टिकोण (स्टैक आधारित)
- एक स्टैक
stपरिभाषित करें जो इंडेक्स स्टोर करेगा। cost := 0- स्ट्रिंग के प्रत्येक कैरेक्टर i के लिए:
- यदि स्टैक खाली नहीं है और
s[st.top()] == s[i](लगातार डुप्लिकेट):- यदि
nums[st.top()] > nums[i], तो सस्ते वाले को हटाएं:cost += nums[i] - अन्यथा:
cost += nums[st.top()], स्टैक से पॉप करें, और वर्तमान इंडेक्स पुश करें।
- यदि
- अन्यथा: वर्तमान इंडेक्स स्टैक में पुश करें।
- यदि स्टैक खाली नहीं है और
costवापस करें।
उदाहरण (C++ कोड)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(string s, vector<int>& nums) {
stack<int> st;
int cost = 0;
for (int i = 0; i < s.size(); ++i) {
if (st.size() && s[st.top()] == s[i]) {
if (nums[st.top()] > nums[i]) {
cost += nums[i];
} else {
cost += nums[st.top()];
st.pop();
st.push(i);
}
} else {
st.push(i);
}
}
return cost;
}
};
int main() {
vector<int> v = {2, 3, 10, 4, 6};
string s = "xxyyx";
cout << (new Solution())->solve(s, v);
return 0;
} इनपुट
"xxyyx", {2,3,10,4,6} आउटपुट
6
