sir i didnot understood the logic behind this algorithm in editorial can i get explanation on it???
Sir i did not understood the logic
Can you please post the editorial code so that I can explain?
because we do not have access to it directly.
#include <bits/stdc++.h>
using namespace std;
void lexicoLarger(string str, string osf, bool flag, string originalString)
{
if (str.size() == 0)
{
if (osf > originalString)
cout << osf << endl;
return;
}
for (int i = 0; i < str.size(); i++)
{
string ros = str.substr(0, i) + str.substr(i + 1);
char ch = str[i];
if (flag)
{
lexicoLarger(ros, osf + ch, flag, originalString);
}
else
{
if (str[i] >= str[0])
{
lexicoLarger(ros, osf + ch, flag or ch > str[0], originalString);
}
else if (str[i] < str[0])
{
// No call
}
}
}
}
int main(int argc, char const *argv[])
{
string str;
cin >> str;
string orig = str;
sort(str.begin(), str.end());
lexicoLarger(str, "", false, orig);
return 0;
}
In this approach what they have used is recursion to print all the string which are lexicographically greater than the given string. So if the given string is cat the function would print cta,tac,tca.
What they have done here is take each letter from the string and compare it to first letter of the recursed string. If it greater then append the letter to the starting (lexicographically greater) else no function call as we don not require the smaller ones.