Recursion dictionary

#1

nedd some hints, unable to think

#2

Hello @Divya_321

I will give you an intuition of how to solve a recursive problem.
In this problem you will be given an input string. Let say “babc”
You will write a recursive function, let say “printLarger” is the name of the function.

Assume that the “printLarger” function is already complete and does what it is intended to do. // IMPORTANT

Now strings larger than “babc” are those (we will break the problem into subproblems now)

  1. if first ‘b’ remains as it is and the remaining string is shuffled so that the remaining part after shuffling is now larger.
    so here you can say element at first index remains constant and call “printLarger” for the rest of the string. (because printLarger is complete and it will automatically shuffle the remaining string and print the larger strings.)
  2. first ‘b’ is replaced with something greater than ‘b’ (with an element after ‘b’) and the rest of the string can remain same or it can also be larger than what it is.
    so here use a “for” loop to search for things greater than element at this index and swap the greater element with this element and then call "printLarger"for the rest of the string.

If you still have any doubt, you can leave a reply to this thread and I will get back to you.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

#include
using namespace std;

bool compare(string a,string b){
if(a>b){
return true;
}
return false;
}

void permute(string str,int i,string cpy){
if(str[i]==’\0’){
if(compare(str,cpy)){
cout<<str<<endl;
}
return ;
}
for(int j=i;str[j]!=’\0’;j++){
swap(str[i],str[j]);
permute(str,i+1,cpy);
swap(str[i],str[j]);
}
}

int main(){
string str;
cin>>str;
string cpy = str;
permute(str,0,cpy);
return 0;
}

sorry didn’t got your approach may you write psuedo code of it, meanwhile I tried the above code which able to clear only two test cases please tell me what’s wrong in it

#5

Hello @Divya_321

I am posting 3 different ways to solve this.

FIRST
Most hard to understand

SECOND
Easier to understand then the above one

The second approach is

  1. Sort the string
  2. Consider every permutation in lexicograhical/sorted/dictionary order and print the string
    if it is greater than the string printed BEFORE it.

THIRD
Easiest to understand

The third approach is

  1. Consider every permutation in ANY order and push it in a set
  2. Print the contents of the set which are greater than the original string
    This is the easier but you need to have the knowledge of sets for it.

If you need any help, leave a reply and I will get back to you.