IVN
0%

String好题(2)

Posted on Edited on In
Symbols count in article: 19k Reading time ≈ 17 mins.

String好题选编(2)

340. Longest Substring with At Most K Distinct Characters

typical sliding window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int lengthOfLongestSubstringKDistinct(String s, int k) {
    int max=0;
    int left=0;
    int right=0;
    int n=s.length();
    Map<Character,Integer> map=new HashMap<>();
    while(right<n){
        //[left,right)
        char c=s.charAt(right++);
        map.put(c,map.getOrDefault(c,0)+1);
        while(map.size()>k){
            c=s.charAt(left++);
            map.put(c,map.get(c)-1);
            if(map.get(c)==0){
                map.remove(c);
            }
        }
        if(right-left>max){
            max=right-left;
        }
    }
    return max;
}

394. Decode String

好题！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Part{
    StringBuilder sb;
    int num;
    Part(int num){
        this.sb=new StringBuilder();
        this.num=num;
    }
}

public String decodeString(String s) {
    int n=s.length();
    Deque<Part> stack=new LinkedList<>();
    stack.push(new Part(1));
    int num=0;
    for (int i = 0; i < s.length(); i++) {
        char c=s.charAt(i);
        if(Character.isDigit(c)){
            num=num*10+c-'0';
        }else if(c=='[') {
            stack.push(new Part(num));
            num = 0;
        }else if(c==']'){
            Part p=stack.pop();
            int t=p.num;
            for (int j = 0; j < t; j++) {
                stack.peek().sb.append(p.sb);
            }
        }else{
            stack.peek().sb.append(c);
        }
    }
    return stack.peek().sb.toString();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    class StrItem {
    int num = 0;
    StringBuilder sb = new StringBuilder();
    
    StrItem(int n) {this.num = n;}
}
    public String decodeString(String s) {
        int num = 0;
        Stack<StrItem> stack = new Stack<>();
        stack.push(new StrItem(1));
        for (char c: s.toCharArray())
            switch (c) {
                case '0': case '1': case '2': case '3': case '4':
                case '5': case '6': case '7': case '8': case '9':
                    num = num * 10 + c - '0';
                    break;
                case '[':
                    stack.push(new StrItem(num));
                    num = 0;
                    break;
                case ']':
                    String curStr = stack.peek().sb.toString();
                    int n = stack.pop().num;
                    for (int i = 0; i < n; i++)
                        stack.peek().sb.append(curStr);
                    break;
                default:
                    stack.peek().sb.append(c);
            }
        return stack.pop().sb.toString();
    }
}

395. Longest Substring with At Least K Repeating Characters

hardest sliding window?

法一：divide-and-conquer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int longestSubstring(String s, int k) {
    int n=s.length();
    if(k<2){
        return n;
    }
    return helper(s,k,0,n);
}

int helper(String s, int k ,int left, int right){
    if(left>=right){
        return 0;
    }
    int[] counts=new int[26];
    for (int i = left; i < right; i++) {
        counts[s.charAt(i)-'a']++;
    }
    int start=left;
    int end=left;
    int max=0;
    boolean valid=true;
    while(end<right){
        //[left,right)
        char c=s.charAt(end);
        if(counts[c-'a']<k){
            valid=false;
            max=Math.max(max,helper(s,k,start,end));
            start=end+1;
        }
        end++;
    }
    return valid ? right-left : Math.max(max,helper(s,k,start,right));
}

法二：sliding window

402. Remove K Digits

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public String removeKdigits(String num, int k) {
    int n=num.length();
    if(k==n){
        return "0";
    }
    Deque<Integer> stack=new LinkedList<>();
    for (int i = 0; i < n; i++) {
        int cur=num.charAt(i)-'0';
        while(k>0 && !stack.isEmpty() && stack.peek()>cur){
            stack.pop();    //every pop is one delete, i.e, one use of k
            k--;
        }
        stack.push(cur);
    }
    while(k-->0){
        //still have unused k, i.e, can delete more digit to make num smaller
        stack.pop();
    }
    StringBuilder sb=new StringBuilder();
    while(!stack.isEmpty()){
        //1 2 9
        sb.append(stack.pop()); //921
    }
    String res=sb.reverse().toString();
    while(res.length()>1 && res.charAt(0)=='0'){
        res=res.substring(1);
    }
    return res;
}

306. Additive Number

tail recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.math.BigInteger;
class Solution {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();
        for (int i = 1; i <= n / 2; ++i) {
            if (num.charAt(0) == '0' && i > 1) return false;
            BigInteger x1 = new BigInteger(num.substring(0, i));
            for (int j = 1; Math.max(j, i) <= n - i - j; ++j) {
                if (num.charAt(i) == '0' && j > 1) break;
                BigInteger x2 = new BigInteger(num.substring(i, i + j));
                if (isValid(x1, x2, j + i, num)) return true;
            }
        }
        return false;
    }
    private boolean isValid(BigInteger x1, BigInteger x2, int start, String num) {
        if (start == num.length()) return true;
        x2 = x2.add(x1);
        x1 = x2.subtract(x1);
        String sum = x2.toString();
        return num.startsWith(sum, start) && isValid(x1, x2, start + sum.length(), num);
    }
}

227. Basic Calculator II

躲不过的计算器

标准版，不考虑括号

无需中缀转后缀，一个stack就够了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public int calculate(String s) {
    int n=s.length();
    Deque<Integer> stack=new LinkedList<>();
    char sign='+';
    int num=0;
    for (int i = 0; i < n; i++) {
        char c=s.charAt(i);
        if(Character.isDigit(c)){
            num*=10;
            num+=c-'0';
        }
        if(!Character.isDigit(c) && c!=' ' || i==n-1){
            if(sign=='+'){
                stack.push(num);
            }
            if(sign=='-'){
                stack.push(-num);
            }
            if(sign=='*'){
                stack.push(stack.pop()*num);
            }
            if(sign=='/'){
                stack.push(stack.pop()/num);
            }
            num=0;
            sign=c;
        }
    }
    int res=0;
    while(!stack.isEmpty()){
        res+=stack.pop();
    }
    return res;
}

224. Basic Calculator

半升级版，考虑括号，但不再考虑乘除

依然一个stack搞定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int calculate(String s) {
    int n=s.length();
    int sum=0;
    int sign=1;
    Deque<Integer> stack=new LinkedList<>();
    for (int i = 0; i < n; i++) {
        char c=s.charAt(i);
        if(Character.isDigit(c)){
            int num=0;
            while(i<n && Character.isDigit(s.charAt(i))){
                num*=10;
                num+=s.charAt(i)-'0';
                i++;
            }
            i--;
            num*=sign;
            sign=1;
            sum+=num;
        }else if(c=='('){
            stack.push(sum);	//存储上一阶段结果
            stack.push(sign);	//存储这一阶段的符号
            sum=0;
            sign=1;
        }else if(c==')'){
            sum*=stack.pop();
            sum+=stack.pop();
        }else if(c=='-'){
            sign*=-1;
        }
    }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public int calculate(String s) {
    int sum = 0;
    int sign = 1;
    Stack<Integer>st = new Stack<>();
    for(int i = 0;i<s.length();i++){
        char ch = s.charAt(i);
        if(Character.isDigit(ch)){
            int val = 0;
             while(i < s.length() && Character.isDigit(s.charAt(i))){
                 val = val * 10 + (s.charAt(i) - '0');
                 i++;
             }
         i--;
         val = val * sign;
         sign = 1;
         sum += val;   
        }
        else if(ch == '('){
          st.push(sum);
          st.push(sign);
            sum = 0;
            sign = 1;
        }
        else if(ch == ')'){
            sum *= st.pop();
            sum += st.pop();
        }
        else if(ch == '-'){
            sign*= -1;
        }
    }
    return sum;
}

418. Sentence Screen Fitting

still hard to understand !

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int wordsTyping(String[] sentence, int rows, int cols) {
    String str=String.join(" ",sentence)+" ";
    int n=str.length();
    int len=0;
    for (int i = 0; i < rows; i++) {
        len+=cols;
        if(str.charAt(len%n)==' '){
            len++;
        }else{
            while(len>0 && str.charAt((len-1)%n)!=' '){
                len--;
            }
        }
    }
    return len/n;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Returns a new {@code String} composed of copies of the
 * {@code CharSequence elements} joined together with a copy of the
 * specified {@code delimiter}.
 *
 * <blockquote>For example,
 * <pre>{@code
 *     List<String> strings = List.of("Java", "is", "cool");
 *     String message = String.join(" ", strings);
 *     //message returned is: "Java is cool"
 *
 *     Set<String> strings =
 *         new LinkedHashSet<>(List.of("Java", "is", "very", "cool"));
 *     String message = String.join("-", strings);
 *     //message returned is: "Java-is-very-cool"
 * }</pre></blockquote>
 *
 * Note that if an individual element is {@code null}, then {@code "null"} is added.
 *
 * @param  delimiter a sequence of characters that is used to separate each
 *         of the {@code elements} in the resulting {@code String}
 * @param  elements an {@code Iterable} that will have its {@code elements}
 *         joined together.
 *
 * @return a new {@code String} that is composed from the {@code elements}
 *         argument
 *
 * @throws NullPointerException If {@code delimiter} or {@code elements}
 *         is {@code null}
 *
 * @see    #join(CharSequence,CharSequence...)
 * @see    java.util.StringJoiner
 * @since 1.8
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int wordsTyping(String[] sentence, int rows, int cols) {
       if (sentence.length == 0) {
    return 0;
}

// convert string array to a string sentence with space between every word
String str = String.join(" ", sentence) + " ";
int n = str.length();
int lenSum = 0;
for (int i = 0; i < rows; i++) {
    lenSum += cols;
    // if last character is space, add effective length by 1, since we put a space after input sentence before
    if (str.charAt(lenSum % n) == ' ') {
        lenSum++;
    }
    // otherwise, find the most recent space position
    else {
        // DO NOT FORGET to MOD n since we may repeat many times of entire sentence in a single line
        while (lenSum > 0 && str.charAt((lenSum - 1) % n) != ' ') {
            lenSum--;
        }
    }
}
return lenSum / n; 
}

415. Add Strings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public String addStrings(String num1, String num2) {
    int n1=num1.length();
    int n2=num2.length();
    StringBuilder sb=new StringBuilder();
    int pre=0;
    for (int i = 1; i <= Math.max(n1, n2); i++) {
        int c1=n1-i>=0 ? num1.charAt(n1-i)-'0' : 0;
        int c2=n2-i>=0 ? num2.charAt(n2-i)-'0' : 0;
        int cur=c1+c2+pre;
        pre=cur/10;
        sb.append(cur%10);
    }
    if(pre!=0){
        sb.append(pre);
    }
    return sb.reverse().toString();
}

484. Find Permutation

Given a string s, reconstruct the lexicographically smallest permutation perm and return it.

思路：

  1. 要想结果最小，则要尽可能把小的数字放前面
  2. 即：发现有increase，则立即出掉
  3. 若是decrease，则无法出掉，只能先存着
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[] findPermutation(String s) {
    int n=s.length()+1;
    int[] res=new int[n];
    int j=0;
    Deque<Integer> stack=new LinkedList<>();
    for (int i = 1; i <= s.length(); i++) {
        char c=s.charAt(i-1);
        stack.push(i);
        if(c=='I'){
            while(!stack.isEmpty()){
                res[j++]=stack.pop();
            }
        }
    }
    stack.push(s.length()+1);
    while(!stack.isEmpty()){
        res[j++]=stack.pop();
    }
    return res;
}

451. Sort Characters By Frequency

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String frequencySort(String s) {
    int n=s.length();
    Map<Character,Integer> count=new HashMap<>();
    for (int i = 0; i < n; i++) {
        char c=s.charAt(i);
        count.put(c,count.getOrDefault(c,0)+1);
    }
    TreeMap<Integer, List<Character>> map=new TreeMap<>();
    for (Character c : count.keySet()) {
        int freq=count.get(c);
        map.putIfAbsent(freq,new ArrayList<>());
        map.get(freq).add(c);
    }
    StringBuilder sb=new StringBuilder();
    for (Integer f : map.keySet()) {
        for (Character c : map.get(f)) {
            for (int j = 0; j < f; j++) {
                sb.append(c);
            }
        }
    }
    return sb.reverse().toString();
}

556. Next Greater Element III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public int nextGreaterElement(int n) {
    //first non-ascending i
    //first j > i
    //swap i,j
    //reverse [i+1,end]
    //163542
    //164532
    //164235
    //14321
    if(n==Integer.MAX_VALUE){
        return -1;
    }
    String s=String.valueOf(n);
    int len=s.length();
    int[] nums=new int[len];
    for (int i = 0; i < len; i++) {
        nums[i]=s.charAt(i)-'0';
    }
    int i=len-1;
    while(i>0 && nums[i-1]>=nums[i]){
        i--;
    }
    i--;
    if(i<0){
        return -1;
    }
    int j=len-1;
    for(; j>i; j--){
        if(nums[j]>nums[i]){
            break;
        }
    }
    swap(nums,i,j);
    reverse(nums,i+1,len-1);
    StringBuilder sb=new StringBuilder();
    for (int num : nums) {
        sb.append(num);
    }
    long res = Long.valueOf(sb.toString());
    return res<=Integer.MAX_VALUE ? (int)res : -1;
}


void reverse(int[] nums, int start, int end){
    while(start<end){
        swap(nums,start++,end--);
    }
}

void swap(int[] nums, int i, int j){
    int temp=nums[i];
    nums[i]=nums[j];
    nums[j]=temp;
}

583. Delete Operation for Two Strings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int minDistance(String word1, String word2) {
    int n1=word1.length();
    int n2=word2.length();
    int[][] dp=new int[n1+1][n2+1];
    //0 1 ... n2
    //1
    //...
    //n1
    for (int i = 1; i <= n1; i++) {
        dp[i][0]=i;
    }
    for (int i = 1; i <= n2; i++) {
        dp[0][i]=i;
    }
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if(word1.charAt(i-1)==word2.charAt(j-1)){
                dp[i][j]=dp[i-1][j-1];
            }else{
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+1;
            }
        }
    }
    return dp[n1][n2];
}

467. Unique Substrings in Wraparound String

Brute Force超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int findSubstringInWraproundString(String p) {
    int n=p.length();
    Set<String> set=new HashSet<>();
    for (int i = 0; i < n; i++) {
        StringBuilder sb=new StringBuilder();
        for (int j = i; j < n; j++) {
            char cur=p.charAt(j);
            if(sb.length()>0){
                char last=sb.charAt(sb.length()-1);
                if(!(last=='z' && cur=='a' || cur-last==1)){
                    break;
                }
            }
            sb.append(cur);
            set.add(sb.toString());
        }
    }
    return set.size();
}

https://leetcode.com/problems/unique-substrings-in-wraparound-string/discuss/95439/Concise-Java-solution-using-DP

另类DP:

  • 子问题为由每个字母结尾的 longest continuous substring
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int findSubstringInWraproundString(String p) {
    int n=p.length();
    int[] arr=new int[26];
    int cur=0;
    for (int i = 0; i < n; i++) {
        if(cur==0 || p.charAt(i-1)=='z' && p.charAt(i)=='a'
                || p.charAt(i)-p.charAt(i-1)==1){
            cur++;
        }else{
            cur=1;
        }
        int idx=p.charAt(i)-'a';
        arr[idx]=Math.max(arr[idx],cur);
    }
    int res=0;
    for (int i = 0; i < 26; i++) {
        res+=arr[i];
    }
    return res;
}

2546. Apply Bitwise Operations to Make Strings Equal

https://leetcode.com/problems/apply-bitwise-operations-to-make-strings-equal/discuss/3083831/JavaC%2B%2BPython-1-line-Check-1

Enumerate the values for s[i] and s[j]
(0, 0) -> (0, 0)
(1, 0) -> (1, 1)
(0, 1) -> (1, 1)
(1, 1) -> (1, 0)

To summrize the rule

  1. Two 0s stay 0s.
  2. If we have 1, we can make any 0 to 1.
  3. If we have at least two 1s, we can make any 1 to 0.

Continue to sunmmrize

  1. All 0 string can not change.
  2. Any other strings can transform from each other.

So we only need to check
if s has 1.
if target has 1.

1
2
3
public boolean makeStringsEqual(String s, String target) {
    return s.contains("1")==target.contains("1");
}

2531. Make Number of Distinct Characters Equal

every possible swap, 26*26

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public boolean isItPossible(String word1, String word2) {
    int[] arr1=new int[26];
    int[] arr2=new int[26];
    int count1=0;
    int count2=0;
    for (int i = 0; i < word1.length(); i++) {
        char c=word1.charAt(i);
        if(arr1[c-'a']==0){
            count1++;
        }
        arr1[c-'a']++;
    }
    for (int i = 0; i < word2.length(); i++) {
        char c=word2.charAt(i);
        if(arr2[c-'a']==0){
            count2++;
        }
        arr2[c-'a']++;
    }
    for (int i = 0; i < 26; i++) {
        if(arr1[i]==0){
            continue;
        }
        for (int j = 0; j < 26; j++) {
            if(arr2[j]==0){
                continue;
            }
            if(i==j && count1==count2){
                return true;
            }
            int a=count1;
            if(arr1[i]==1){
                a--;
            }
            if(arr1[j]==0 || arr1[i]==1 && i==j){
                a++;
            }
            int b=count2;
            if(arr2[j]==1){
                b--;
            }
            if(arr2[i]==0 || arr2[j]==1 && i==j){
                b++;
            }
            if(a==b){
                return true;
            }
        }
    }
    return false;
}

763. Partition Labels

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<Integer> partitionLabels(String s) {
    List<Integer> res=new ArrayList<>();
    int n=s.length();
    char[] chars=s.toCharArray();
    int[] last=new int[26];
    for (int i = 0; i < n; i++) {
        last[chars[i]-'a']=i;
    }
    Set<Integer> set=new HashSet<>();
    int start=0;
    for (int i = 0; i < n; i++) {
        set.add(chars[i]-'a');
        boolean valid=true;
        for (int idx : set) {
            if(last[idx]>i){
                valid=false;
                break;
            }
        }
        if(valid){
            res.add(i-start+1);
            start=i+1;
            set.clear();
        }
    }
    return res;
}

647. Palindromic Substrings

好题好解，一鸭三吃！

Approach #1: Check All Substrings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int countSubstrings(String s) {
    int n=s.length();
    char[] chars=s.toCharArray();
    int res=0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if(isPalindrome(chars,j,i)){
                res++;
            }
        }
    }
    return res;
}

boolean isPalindrome(char[] chars, int j, int i){
    if(j==i){
        return true;
    }
    while(j<=i){
        if(chars[j]!=chars[i]){
            return false;
        }
        j++;
        i--;
    }
    return true;
}

Approach #3: Expand Around Possible Centers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int countSubstrings(String s) {
    int n=s.length();
    int res=0;
    for (int i = 0; i < n; i++) {
        res+=count(s,i,i)+count(s,i,i+1);
    }
    return res;
}

int count(String s, int left, int right){
    int res=0;
    while(left>=0 && right<s.length()
            && s.charAt(left)==s.charAt(right)){
        left--;
        right++;
        res++;
    }
    return res;
}

524. Longest Word in Dictionary through Deleting

through deleting ? just skipping!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String findLongestWord(String s, List<String> dictionary) {
    int n=s.length();
    Collections.sort(dictionary, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o1.length()!=o2.length() ? o2.length()-o1.length() : o1.compareTo(o2);
        }
    });
    for (String word : dictionary) {
        int idx=0;
        for (int i = 0; i < n; i++) {
            if(s.charAt(i)==word.charAt(idx)){
                idx++;
                if(idx==word.length()){
                    return word;
                }
            }
        }
    }
    return "";
}

720. Longest Word in Dictionary

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public String longestWord(String[] words) {
    int n= words.length;
    Arrays.sort(words,(a,b)->(a.length()!=b.length() ? b.length()-a.length() : a.compareTo(b)));
    Set<String> set=new HashSet<>(Arrays.asList(words));
    for (int i = 0; i < n; i++) {
        String word=words[i];
        int j=0;
        for (; j < word.length(); j++) {
            if(!set.contains(word.substring(0,j+1))){
                break;
            }
        }
        if(j==word.length()){
            return word;
        }
    }
    return "";
}

767. Reorganize String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public String reorganizeString(String s) {
    char[] chars = s.toCharArray();
    int[] arr=new int[26];
    int n=s.length();
    for (char c : chars) {
        arr[c-'a']++;
    }
    int max=0;
    int maxIdx=0;
    for (int i = 0; i < 26; i++) {
        if(arr[i]>max){
            max=arr[i];
            maxIdx=i;
        }
    }
    //2 3   2 4
    //3 4
    if(max>(n+1)/2){
        return "";
    }
    int idx=0;
    while(arr[maxIdx]>0){
        chars[idx]=(char)('a'+maxIdx);
        idx+=2;
        arr[maxIdx]--;
    }
    for (int i = 0; i < 26; i++) {
        while(arr[i]>0){
            if(idx>=n){
                idx=1;
            }
            chars[idx]=(char)('a'+i);
            arr[i]--;
            idx+=2;
        }
    }
    return new String(chars);
}

937. Reorder Data in Log Files

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public String[] reorderLogFiles(String[] logs) {
    List<Integer> digits=new ArrayList<>();
    //[string,identifier,content]
    PriorityQueue<String[]> pq=new PriorityQueue<>(
            new Comparator<String[]>() {
                @Override
                public int compare(String[] a, String[] b) {
                    if(a[2].equals(b[2])){
                        return a[1].compareTo(b[1]);
                    }
                    return a[2].compareTo(b[2]);
                }
            }
    );
    int n=logs.length;
    for (int j=0; j<n; j++) {
        String log=logs[j];
        int idx=log.indexOf(" ");
        String identifier=log.substring(0,idx);
        String content=log.substring(idx+1);
        boolean isDigit=Character.isDigit(content.charAt(0));
        if(isDigit){
            digits.add(j);
        }else{
            pq.offer(new String[]{log,identifier,content});
        }
    }
    String[] res=new String[n];
    int i=0;
    while(!pq.isEmpty()){
        res[i++]=pq.poll()[0];
    }
    int idx=0;
    while(i<n){
        res[i++]=logs[digits.get(idx++)];
    }
    return res;
}