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;
}