TheJobOverflow | Oracle OA | IIIT Bhubaneswar | Good Subsequences | Modify the String | Longest Increasing Subsequence | FTE

5

Entering edit mode

ADD COMMENT • link

6

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/

ADD COMMENT • link 2.3 years ago Raunit Verma • 90

2

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;
}

ADD COMMENT • link 2.3 years ago Captain Stark • 20

1

Entering edit mode

LIS

int lengthOfLIS(vector<int>& arr) {

int ans=1,n=arr.size();

vector<int>dp(n,1);

for(int i=1;i<n;i++)

{

for(int j=0;j<i;j++)

{

if(arr[i]>arr[j])

{

dp[i]=max(dp[i],dp[j]+1);

ans=max(ans,dp[i]);

}

return ans;

}

ADD COMMENT • link 2.3 years ago Gurshruti singh sidh • 10

0

Entering edit mode

How many were shortlisted?

ADD COMMENT • link 2.3 years ago Malang • 0

Login before adding your answer.