Saturday, 16 Oct 2021

# Lexicographically largest subsequence containing all distinct characters only once

Given a string S, the task is to find the lexicographically largest subsequence that can be formed using all distinct characters only once from the given string.Examples:Input: S = ababcOutput: bacExplanation:All possible subsequences containing all the characters in S exactly once are {“abc”, “bac”}. The lexicograohically maximum among all the subsequences  is “bac”.Input: S = “zydsbacab”Output: zydscabApproach: The given problem can be solved using Stack. The idea is to traverse the string and store those characters in the stack in lexicographically largest order so as to generate the resultant string. Follow the steps below to solve the given problem:Below is the implementation of the above approach:C++  #include using namespace std;  string lexicoMaxSubsequence(string s, int n){    stack st;              vector visited(26, 0), cnt(26, 0);              for (int i = 0; i < n; i++) {        cnt[s[i] - 'a']++;    }    for (int i = 0; i < n; i++) {                          cnt[s[i] - 'a']--;                          if (visited[s[i] - 'a']) {            continue;        }                                  while (!st.empty() && st.top() < s[i]               && cnt[st.top() - 'a'] != 0) {            visited[st.top() - 'a'] = 0;            st.pop();        }                  st.push(s[i]);        visited[s[i] - 'a'] = 1;    }          string s1;          while (!st.empty()) {        s1 = st.top() + s1;        st.pop();    }          return s1;}  int main(){    string S = "ababc";    int N = S.length();    cout