 # Why Simple Greedy Fails For Larger Test Cases?

#1

Approach
If we want to make lexico wise largest we just take the ith char and take maximum char from its rights which is greater than A[i] and swap it.

Problem: Failing for Larger Test Cases ??? Please Correct me

``````string Solution::solve(string A, int B) {
for(int i=0;i<A.length();i++){
char x=A[i];
int idx=i;
for(int j=i+1;j<A.length();j++){
if(A[j]>A[i]){
if(x<A[j]){
x=A[j]; idx=j;
}
}
}
if(x!=A[i]){
swap(A[idx],A[i]);
B--;
}
if(!B) return A;
}

return A;
}
``````

#2

I too have the same doubt.

#3

@anshuman-srivastava Consider string A=“2488” and B=2. Your output fails

#4

Hey, I have taken care of such cases in my code but its still says fails for larger cases. Can you help?
Here is my code :-

Summary

int counting(string a, auto &maxi){
int count = 0;
auto it = a.begin();
while(it < a.end()){
if(*it == *maxi)
count++;
it++;
}
return count;
}

string solve(string a, int b)
{
int n = a.size();
if(n == 0)return “”;
if(b >= n-1){
sort(a.rbegin(), a.rend());
return a;
}
int i = 0;
string res = “”;
while(b && i < n){
auto maxi = max_element(a.rbegin(), a.rend());
res += *maxi;
if(*maxi != *a.begin()){
int count = min(b, counting(a, maxi));
sort(a.begin(), a.begin()+count);
swap(*a.begin(), *maxi);
b–;
}
a.erase(a.begin());
i++;
}
return res+a;
}