Codeforces Round #705 K-beautiful Strings

Solution

Of course greedy. But it's very clear. So more a implementation problem.

First of all, if $n\ mod\ k\ne{0}$, then must be -1
If s is beautiful, then just print s.
Then the problem start:
1. Let's find the fisrt point which different from s. We find this point from end to begin. Because we want our string as small as possible.
2. Once we chose the first point. Then we just put some charts after this point to make our string match the requirement.

But there are many detail logics here.

First of all, "Chose the point"。The points before the "change point" should have enought capability to build a acceptable result.
For example, ddbccc and 3. When we select the change point to 3(b). If change it to c, then need 1 more d and 2 more c after point 4. But if we change it to d, then no need anything after point 4.
Related code:

    private static int getChangePos() {
        for (int i = n - 1; i >= 1; i--) {
            int now = s[i] - 'a';
            if (now == 25) continue;

            int totalNeed = 0;
            boolean useful = false;
            for (int j = 0; j < 26; j++) {
                int need = getNeed(i - 1, j);
                totalNeed += need;
                if (need != 0 && j > now) {
                    useful = true;
                }
            }
            if (useful) totalNeed -= 1;
            else totalNeed += m - 1;

            int afterMe = n - 1 - i;
            if (totalNeed <= afterMe) {
                return i;
            }
        }
        return 0;
    }

Also the change point not need reduce the needs of the points before. If the points after the change point can handle, then just chose smallest char on change point.
Related logic:

            int afterMe = n - 1 - changeAtMe;

            int currentChar = s[changeAtMe] - 'a';
            int nextChar = currentChar + 1;

            int totalDirectNeed = 0;
            for (int i = 0; i < 26; i++) {
                totalDirectNeed += getNeed(changeAtMe - 1, i);
            }
            if (totalDirectNeed + m - 1 > afterMe) {
                for (int i = nextChar; i < 26; i++) {
                    if (getNeed(changeAtMe - 1, i) != 0) {
                        nextChar = i;
                        break;
                    }
                }
            }

            count[changeAtMe][currentChar]--;
            count[changeAtMe][nextChar]++;
            s[changeAtMe] = (char) (nextChar + 'a');

And the last thing. When solve the needs, should start from end to begin. After solved all needs, just put as much 'a' as we can.

Code

I'm so stupid. This problem is just a simple one. But spent lots of time on it. And Also got few WA before AC.

Codeforces Round #705 K-beautiful Strings - implementation

xloypaypa

Solution

Code