Site Message

Only Premium Users can view the Question

Site Message

Only Premium Users can view the Question

Site Message

Only Premium Users can view the Question

Site Message

Only Premium Users can view the Question

Question: Oracle OA | IIIT Bhubaneswar | Good Subsequences | Modify the String | Longest Increasing Subsequence | FTE | 2023
5
Entering edit mode

ADD COMMENTlink 2.0 years ago Delta 3.0k
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 COMMENTlink 2.0 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 COMMENTlink 2.0 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 COMMENTlink 2.0 years ago Gurshruti singh sidh • 10
0
Entering edit mode

How many were shortlisted?

ADD COMMENTlink 2.0 years ago Malang • 0

Login before adding your answer.

APPLY NOWSimilar Posts
Loading Similar Posts