Join Us
Loading Similar Posts
Entering edit mode
A question similar to MODIFY THE STRING on LeetCode
EXPECTED SOLUTION :
class Solution {
public:
string removeDuplicateLetters(string s) {
stack<char>st;
vector<int>m(26,-1);
vector<bool>v(26,false);
for(int i=0; i<s.length(); i++)m[s[i]-'a']=i;
for(int i=0; i<s.length(); i++){
if(v[s[i]-'a'])continue;
while(!st.empty() && st.top()<s[i] && m[st.top()-'a']>i){
v[st.top()-'a']=false;
st.pop();
}
if(!v[s[i]-'a'])
st.push(s[i]);
v[s[i]-'a']=true;
}
string ans="";
while(!st.empty()){
ans+=st.top();
st.pop();
}
reverse(ans.begin(),ans.end());
return ans;
}
};
https://leetcode.com/problems/remove-duplicate-letters/description/
Entering edit mode
// BackTracking Aprroach
// But I think this acn be further Optimised
#include<bits/stdc++.h>
using namespace std;
int solve(int i,string &s,vector<char>temp){
if(i==s.size()){
vector<int>check(26,0);
for(int i=0;i<temp.size();i++){
check[temp[i]-'a']++;
}
int prev = -1;
for(int i=0;i<26;i++){
if(check[i]!=0){
prev = check[i];
break;
}
}
for(int i=0;i<26;i++){
if(check[i]!=0 && check[i]!=prev)
return 0;
}
return 1;
}
temp.push_back(s[i]);
int pick = solve(i+1,s,temp);
temp.pop_back();
int notpick = solve(i+1,s,temp);
return pick + notpick;
}
int main(){
string s = "baab";
int n = s.size();
int ans = solve(0,s,vector<char>());
cout<<ans-1;
return ans-1;
}
