Ninja Subsequence

Approach : 
 

• We first find all the subsequences of the sequence ‘S’.
• There are ‘2^N’ such subsequences.
• Then we select the set of non-regular subsequences among these of maximum length.
• Then we sort these subsequences.
• If the total number of subsequences is < ‘K’, we return -1.
• Else, we return the ‘Kth’ subsequence among these.

 

Algorithm : 

• Initialise a variable ‘ans’ as ‘0’.
• Initialise a variable ‘maxi’ as ‘0’ which stores the length of maximum non-regular subsequence.
• Run a for loop from ‘i = 0’ to ‘i = 2^N-1’ :
  • Initialise a set ‘st’.
  • Initialise a string ‘tmp’ as empty.
  • Run a loop from ‘j=0’ to ‘j=N-1’.
    • If the ‘jth’ bit is set in ‘i’ :
    • Add ‘S[j]’ to ‘tmp’.
  • Check if the string formed is non-regular :
  • If yes :
    • If ‘maxi’<’tmp.size()’ , update ‘maxi’ to ‘tmp.size()’ and clear set ‘st’.
    • If ‘maxi’ = ‘tmp.size()’ , add ‘tmp’ to ‘st’.
• If the size of the set ‘st’ < ‘K’ :
• Return -1.
• Sort the set of strings by prioritising ‘(‘ before ‘)’.
• Return the ‘Kth’ string of the set.

Approach : 
 

• We first notice that the maximum length non-regular subsequences are less in number.
• If the string ‘S’ is itself non-regular, then there exists only 1 non-regular subsequence of maximum length.
• Else, all the subsequences of length ‘N-1’ will be non-regular.
• So, we only need to think about the second case.
• Since, the whole string is regular. So, by removing any character from the string makes it non-regular.
• Next we notice that since we require distinct subsequences, removing adjacent same characters will produce the same subsequences.
  • Example : If ‘S’ = (()).
  • Removing either the 1st character or the 2nd character will produce the same result : ()).
• So, we only need to remove one of the consecutive same characters from ‘S’.
• Now, we think of some way to remove characters such that we maintain the lexicographic order.
• Since ‘)’ > ‘( lexicographically, we will remove ‘)’ characters first and then ‘(‘ characters.
• Now, we need to decide from where to start removing characters, beginning of the string or the end of it.
• We see greedily that removing ‘)’ characters from beginning and later ‘(‘ characters from the end will produce lexicographically ordered subsequences.
  • Example : If ‘Str’ = “abab”, then removing ‘b’ from beginning and then ‘a’ from end will produce sorted subsequences as “aab”, “aba” , “abb” , and “bab”.
  • Similar pattern exists from string with parentheses as character.
• At each character which can be removed, we decrement ‘K’.
• When ‘K=0’ , we remove the character and return the remaining string.
• If ‘K>0’ after all removals, we return “-1”.

Algorithm : 
 

• Check if the input string ‘S’ is regular.
• If not :
  • If ‘K=1’ return ‘S’, else return “-1”.
• Else :
• Run a loop from ‘i=0’ to ‘i=N-1’ :
  • Initialize a variable ‘j’ = ‘i’ :
  • Keep incrementing ‘j’ till ‘j<N’ and ‘S[j]’ = ‘S[i]’.
  • If ‘S[i]’ = ‘)’ :
    • Decrement ‘K’.
    • If ‘K=0’ :
    • Initialise a string ‘ans’ with substring(0,i) + substring(i+1).
    • Return ‘ans’.
  • Assign ‘i=j’.
• Run a loop from ‘i=N-1’ to ‘i=0’ :
  • Initialize a variable ‘j’ = ‘i’ :
  • Keep decrementing ‘j’ till ‘j>=0’ and ‘S[j]’ = ‘S[i]’.
  • If ‘S[i]’ = ‘(’ :
    • Decrement ‘K’.
    • If ‘K=0’ :
    • Initialise a string ‘ans’ with substring(0,i) + substring(i+1).
    • Return ‘ans’.
  • Assign ‘i=j’.
• If we reach here, return “-1”.