Java Solution with Explanations (66ms beats 90%)


  • 0

    To achieve max lexico order, there is one observation came into mind: except the cutting word, all other words must be lexico maximum. So this leads to the first piece of code, just make each word lexico maximum.

    Then there is second observation: the first char after the cutting point must be of largest Character. So here comes the second piece of code to scan across to find the largest Character and its positions.

    Here I remember three indices: the final index, the string's idx and the char idx within string. These indices will be used later.

    Now we iterate those indices of cutting point and try each one to see if we can get max lexico one. Here comes some tricks, we must try both original and reversed order for cutting word. So try it twice.

    I am surprised I achieve 90% in AC, probably because there are less submissions for a new problem.

    Actually I am not satisfied with the solution, it is kind of verbose. And the worst case complexity is O(total len^2).

    public class Solution {
        
        private String reverse(String str) {
            return new StringBuilder(str).reverse().toString();
        }
        
        public String splitLoopedString(String[] strs) {
            for(int i=0; i<strs.length; i++) {
                String reversed = reverse(strs[i]);
                if(strs[i].compareTo(reversed) < 0)
                    strs[i] = reversed;
            }
            
            StringBuilder sb = new StringBuilder();
            int len = 0;
            char maxChar = 'a'-1;
            List<int[]> maxIdx = new ArrayList<>();
            for(int i=0; i<strs.length; i++) {
                sb.append(strs[i]);
                for(int j=0; j<strs[i].length(); j++) {
                    char c = strs[i].charAt(j);
                    if(c == maxChar)
                        maxIdx.add(new int[]{len, i, j});
                    else if(c > maxChar) {
                        maxChar = c;
                        maxIdx = new ArrayList<>();
                        maxIdx.add(new int[]{len, i, j});
                    }
                    len++;
                }
            }
            String maxStr = sb.toString();
            for(int[] idx : maxIdx) {
                int i = idx[0], strI = idx[1], charI = idx[2];
                String str1 = sb.substring(i) + sb.substring(0,i);
                // e.g. full str = "abc deyfg hij" where cut just before y
                // The alternative str = "abc gfyed hij"
                String str2 = maxChar + // y
                              reverse(strs[strI].substring(0,charI)) + // de's reverse -> ed
                              sb.substring(i+strs[strI].length()-charI) + // hij
                              sb.substring(0,i-charI) + // abc
                              reverse(strs[strI].substring(charI+1)); // fg's reverse -> gf
                if(str1.compareTo(maxStr) >0)
                    maxStr = str1;
                if(str2.compareTo(maxStr) >0)
                    maxStr = str2;
            }
            
            return maxStr;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.