MinLexSwap

string MinLexSwap(string s)
{
    int len = s.size();
    int loccur[26];
    memset(loccur, -1, sizeof(loccur));
    for(int i = len - 1; i >= 0; --i)
    {
        int chI = s[i] - 'a';
        if(loccur[chI] == -1)
            loccur[chI] = i;
    }
    string sorted_s = s;
    sort(sorted_s.begin(), sorted_s.end());
    if(sorted_s==s)
    {
        int i=len-1;
        while(s[i]==s[i-1] && i>0)
            i--;
        if(i>0)
            swap(s[i],s[i-1]);

    }
    else
    {
        for(int i = 0; i < len; ++i)
        {
            if(s[i]!= sorted_s[i])
            {
                int chI = sorted_s[i] - 'a';
                int last_occ = loccur[chI];
                swap(s[i], s[last_occ]);
                break;
            }
        }
    }
    return s;
}

/**
so
string MinLexSwap(string s)
{
    int i, j, n;
    string t;
    n = s.length();
    t = s;
    sort(t.begin(), t.end());
    if (s == t) /// s este ordonat crescator
    {
        j = i = n - 1;
        while (s[j] == s[i])
            j--;
        swap(s[j + 1], s[j]);
        return s;
    }
    for (i = 0; s[i] == t[i]; i++)
        ;
    for (j = n - 1; s[j] != t[i]; j--)
        ;
    swap(s[i], s[j]);
    return s;
}
*/