【力扣】3403. 从盒子中找出字典序最大的字符串 I

解法一：

class Solution {
    public String answerString(String word, int numFriends) {
        //对字符的划分，word长度为n，共有n+1个位置可以插入，但是要求被分为非空字符串，所以插入的位置最多为n-1。
        int n = word.length();//字符串长度
        //字符数组存储分解下的字符串
        //分解个数等于长度，每个一个字母
        if (numFriends == 1){
            return word;
        }
        String max = "";
        //可以取出来的时候直接比较！，不必浪费空间去存储！
        //而这道题的思路并不是让我直接全部取出来比较
        //而是考虑一个问题：以某个位置i为起点可以截取的的字符串，其长度越大，字典序也就越大
        //根据n和numfriends,可以得到这个字符串在这个情况下可以截取的最大长度，直接将该长度拿出来即可！！！！！
        //而这个最大长度应该是min(n-numfriends+1,n-i)
        for (int i = 0; i < n; i++) {
            String str = word.substring(i,Math.min(n+i-numFriends+1,n));
            max = max.compareTo(str) >=0 ? max : str ;


        }
        return max;
    }
}

总结：在这里我犯了一个错误，关于最大长度min(n-numfriends+1,n-i)，确实是最大长度，但是从第i个位置开始的最大长度，那么我还应该加上i,所以代码中是min(n+i-numFriends+1,n)，n-i:当前长度到字符串末尾还剩的长度，有可能不足可以取的最大长度
反思：善于从题目中提取信息后转化为数学问题（而这道题的思路并不是让我直接全部取出来比较，而是考虑一个问题：以某个位置i为起点可以截取的的字符串，其长度越大，字典序也就越大，所以仅需将从某个位置开始的可以取的最大长度取出来比较即可）

解法二：双指针

class Solution {
    public String lastSubstring(String s) {
        int i = 0, j = 1, n = s.length();
        while (j < n) {
            int k = 0;
            while (j + k < n && s.charAt(i + k) == s.charAt(j + k)) {
                k++;
            }
            if (j + k < n && s.charAt(i + k) < s.charAt(j + k)) {
                int t = i;
                i = j;
                j = Math.max(j + 1, t + k + 1);
            } else {
                j = j + k + 1;
            }
        }
        return s.substring(i);
    }

    public String answerString(String word, int numFriends) {
        if (numFriends == 1) {
            return word;
        }
        String last = lastSubstring(word);
        int n = word.length(), m = last.length();
        return last.substring(0, Math.min(m, n - numFriends + 1));
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/find-the-lexicographically-largest-string-from-the-box-i/solutions/3685906/cong-he-zi-zhong-zhao-chu-zi-dian-xu-zui-eg0v/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。