leetcode
leetcode 1001 ~ 1050
按字典序排在最后的子串

按字典序排在最后的子串

难度:

标签:

题目描述

代码结果

运行时间: 198 ms, 内存: 18.4 MB


/*
 * 题目思路:
 * 1. 使用Java Stream API简化操作。
 * 2. 使用IntStream生成所有可能的起始点。
 * 3. 将每个起始点生成的子串收集到一个列表中。
 * 4. 找到列表中字典序最大的子串。
 */

import java.util.stream.IntStream;
import java.util.Collections;
import java.util.List;

public class Solution {
    public String lastSubstring(String s) {
        List<String> substrings = IntStream.range(0, s.length())
                                            .mapToObj(s::substring)
                                            .collect(Collectors.toList());
        return Collections.max(substrings);
    }
}

解释

方法:

此题解采用了一种高效的字符串比较策略,目标是找到按字典序排在最后的子串。算法使用两个指针i和j,以及一个偏移量k。指针i始终指向当前认为可能是最大字典序子串的起始位置,而j则用来探索其他可能的起始位置。通过比较s[i+k]与s[j+k],算法决定如何移动i或j:若s[i+k]小于s[j+k],则更新i到当前j的位置,因为从j开始的子串具有更大的字典序。若s[i+k]大于s[j+k],则j向后移动,因为i处的子串仍然是潜在的最大字典序子串。整个过程一直进行,直到j+k等于字符串长度n,此时i处的子串就是所求的最大字典序子串。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
如何确保算法在s[i+k]小于s[j+k]时将i更新到j而不是j+k的位置?这样的更新对算法的正确性有何影响?
当s[i+k]小于s[j+k]时,说明从位置j开始的子串具有更大的字典序。因此,将i更新到j的位置而不是j+k,是为了重新开始比较从j开始的新子串与当前已知的最大字典序子串。如果更新至j+k,则会跳过j到j+k之间的所有潜在的最大字典序子串的起始位置。这种更新确保了算法不会遗漏可能的最大字典序子串,从而保持算法的正确性。
🦆
在比较s[i+k]与s[j+k]时,如果两个字符相等,为什么选择增加偏移量k而不是直接移动i或j?这样做有什么优势?
当s[i+k]和s[j+k]相等时,增加偏移量k可以继续比较后续的字符,以确定哪个子串具有更大的字典序。如果直接移动i或j,将无法比较完整的子串,可能会错过更高字典序的子串。通过增加k,可以在不丢失当前比较基准的情况下,细致地比较两个子串,这增加了算法的精确度和准确性。
🦆
算法中提到,一旦k被重置,j会移动到i+1的位置,但如果i已经是j-1,这种情况下i和j的更新逻辑是怎样的?
当i为j-1时,并且需要更新i到j的位置,实际上i和j已经非常接近,指向连续的两个字符。在这种情况下,更新i到j之后,j会被设置到i+1,即新的i位置的下一个位置。这避免了i和j重叠,保证了j始终在探索新的潜在最大字典序子串的起始位置。
🦆
整个算法在遇到所有字符都相同的字符串,如'aaaaa'时的表现如何?是否存在效率低下的风险?
在所有字符都相同的字符串情况下,算法效率确实较低。因为s[i+k]和s[j+k]始终相等,导致偏移量k不断增加直到j+k达到字符串的末尾。这种情况下,算法的时间复杂度接近O(n^2),因为每次对比都是在逐渐增加k,直到整个字符串结束。这样的线性比较在字符完全相同的情况下会导致效率低下。

相关问题