Topic describes

Given a string s, please reconstruct the string according to the following algorithm:

1. Select the smallest character from s and append it to the result string. 2. Select the smallest character from the remaining s character, which is larger than the last added character, and append it to the result string. 3. Repeat step 2 until you cannot select a character from s. 4. Select the largest character from s and append it to the result string. 5. Select the largest character from the remaining s character, which is smaller than the last added character, and append it to the result string. 6. Repeat step 5 until you cannot select a character from s. 7. Repeat steps 1 through 6 until all characters in S are selected. In any step, if there is more than one minimum or maximum character, you can select either and add it to the resulting string.

Return the result string after reordering the characters in S.

  • prompt
  • 1 <= s.length <= 500
  • The s contains only lowercase letters.

The sample

Example 1:

Enter: s ="aaaabbbbcccc"Output:"abccbaabccba"Explanation: Steps for the first round1.2.3The result string is result ="abc"Steps for the first round4.5.6The result string is result ="abccba"The first round is over, and now s is equal to"aabbcc", let's go back to the steps1Steps for the second round1.2.3The result string is result ="abccbaabc"Steps for the second round4.5.6The result string is result ="abccbaabccba"
Copy the code

Example 2:

Enter: s ="leetcode"Output:"cdelotee"
Copy the code

Answer key

This problem, after careful analysis, in fact, in two steps, first in ascending order of all characters, and then in descending order of all characters. Each permutation takes a number of letters. The prerequisite is that the original string contains only 26 English letters and may be duplicated.

The first step is to analyze your thinking

After analyzing this, the first step is to sort out the solution: think of it this way: break up the original string and put it into a container, one by one. The container is 26 empty Spaces, in the order of A to Z.

Step two, data structure

How do you do that? We can define a 26-length array like this. We know the Unicode encoding for ‘a’. ‘a’.charcodeat () is equal to 97, and 97 is the smallest of the 26 characters. Num [I]++ = num[I]++ = num[I]+ = num[I]+ = num[I]+ = num[I]+ = num[I]+ = num[I]+ = num[I]+ This part of the code looks like this:

var s = 'aaabbbcccaa'
const num = new Array(26).fill(0);
for (let ch of s) {
        num[ch.charCodeAt() - 'a'.charCodeAt()]++;
    }
/ / num =,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 [5]
Copy the code

Step three, traverse

Given num, we can perform the operations described in the problem, one ascending, one descending; The ascending order is from 0 to 25, and the descending order is from 25 to 0. Num [I]– once until the value of num[I] is 0;

At this point, the idea is obvious, and the code expression looks like this:

let ret = ' ';
    while (ret.length < s.length) {
        for (let i = 0; i < 26; i++) {
            if (num[i]) {
                ret += String.fromCharCode(i + 'a'.charCodeAt()); num[i]--; }}for (let i = 25; i >= 0; i--) {
            if (num[i]) {
                ret += String.fromCharCode(i + 'a'.charCodeAt()); num[i]--; }}}return ret;
Copy the code

Num = fromCharCodeAt; fromCharCode = fromCharCode; num = fromCharCode; Here’s the full code:

var sortString = function(s) {
    const num = new Array(26).fill(0);
    for (let ch of s) {
        num[ch.charCodeAt() - 'a'.charCodeAt()]++;
    }

    let ret = ' ';
    while (ret.length < s.length) {
        for (let i = 0; i < 26; i++) {
            if (num[i]) {
                ret += String.fromCharCode(i + 'a'.charCodeAt()); num[i]--; }}for (let i = 25; i >= 0; i--) {
            if (num[i]) {
                ret += String.fromCharCode(i + 'a'.charCodeAt()); num[i]--; }}}return ret;
};
Copy the code

Source: LeetCode link: leetcode-cn.com/problems/in…