Java 中不重复字符的最长子串长度

2024年9月10日 | 11 分钟阅读

发现无重复字符的最长子串的长度是一项在算法编程中至关重要的挑战。该问题涉及识别给定字符串中每个字符仅出现一次的连续部分的 the 长度。在 Java 编程环境中解决此挑战需要熟练运用字符串操作工具和算法范例。该问题在优化计算过程方面非常实用，尤其是在数据压缩和字符串处理场景中。

示例 1

输入： "pqrstuvwxy"

输出 10

解释： 整个字符串 "pqrstuvwxy" 没有重复字符，构成最长的子串，长度为 10。

示例 2

输入： "abacabadabacaba"

输出 4

解释： 无重复字符的不同的子串是 "abac" 和 "bacab"，长度为 4。

示例 3

输入： "xyzxyzabcd"

输出 6

解释： 无重复字符的最长子串是 "xyzabc" 和 "yzabcd"，长度均为 6。

示例 4

输入： "mississippi"

输出 4

解释： 无重复字符的最长子串是 "issi"，长度为 4。

方法：使用滑动窗口，时间复杂度 O(n3)。

滑动窗口方法用于在 O(n3) 时间内查找最长无重复字符子串的长度，它通过在文本中移动窗口来检查子串。

算法

步骤 1： 将输入字符串 s 的长度设为 n，将 maxLength 设为 0。

步骤 2： 使用索引为 i 从 0 到 n 的循环遍历子串的所有可能起始索引。

对于每个 i，使用索引为 j 从 i + 1 到 n 的嵌套循环遍历子串的所有可能结束索引。
调用 allUnique 方法来验证从索引 i 到 j - 1 的子串中的所有字符是否唯一。

步骤 3： allUnique 方法使用两个嵌套循环遍历子串，将每个字符与其他所有字符进行比较。

步骤 4： 如果找到重复字符，则返回 false；否则返回 true。

步骤 5： 如果子串是唯一的（allUnique 返回 true），则计算子串的长度 (j - i) 并使用其当前值和计算出的长度的最大值来更新 maxLength。

步骤 6： 两个循环完成后，返回 maxLength 的最终值，即最长无重复字符子串的长度。

步骤 7： 检查给定子串（从索引 start 到 end - 1）中的所有字符是否唯一。

使用两个嵌套循环将子串中的每个字符与其他每个字符进行比较。

步骤 8： 显示代码结果。

实施

文件名： LongestSubstring1.java

public class LongestSubstring1 {

    //Method to find the length of the longest substring without repeating characters
    public static int lengthOfLongestSubstring(String s) {
        int n = s.length(); // Get the length of the input string
        int maxLength = 0; //Initialize the maximum length of the substring

        // Iterate through all possible substrings
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (allUnique(s, i, j)) {
                    maxLength = Math.max(maxLength, j - i); // Update the maximum length if the substring is unique
                }
            }
        }

        return maxLength; // Return the maximum length of the substring
    }

    // Helper method to check if all characters in a substring are unique
    private static boolean allUnique(String s, int start, int end) {
        for (int i = start; i < end - 1; i++) {
            for (int j = i + 1; j < end; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    return false; // Return false if any characters are repeated
                }
            }
        }
        return true; // Return true if all characters are unique
    }

    // Main Method for testing the algorithm
    public static void main(String[] args) {
        String input = "javatpoint"; // Set the input string
        int result = lengthOfLongestSubstring(input); // Call the method to find the result

        // Display the result
        System.out.println("Length of the longest substring without repeating characters: " + result);
    }
}

输出

Length of the longest substring without repeating characters: 7

时间复杂度： 所提供代码的时间复杂度为 O(n3)，其中 'n' 是输入字符串的长度。

辅助空间： 辅助空间复杂度为 O(1) 或常数空间。此外，辅助方法 allUnique 只使用少量局部变量，并且其空间复杂度与输入大小无关，始终保持常数。

方法：使用滑动窗口，时间复杂度 O(n2)

滑动窗口方法用于在 O(n2) 时间内查找最长无重复字符子串的长度，它会有效地调整输入字符串上的窗口，适用于中等规模的输入。

算法

步骤 1： 导入必要的包：导入 java.io.* 用于输入/输出功能，并导入 java.util.*。

步骤 2： 定义 lengthOfLongestSubstring 方法，以及 String s 的输入和 Integer 的输出（最长无重复字符子串的长度）

步骤 3： 现在初始化变量。将输入字符串 s 的长度设为 n，并将 maxLength 设为 0。

步骤 4： 开始一个索引为 i 从 0 到 n - 1 的循环。

对于外层循环中的每个 i，启动一个索引为 j 从 i + 1 到 n 的嵌套循环。

步骤 5： 创建一个大小为 256 的布尔数组 visited，用于使用 ASCII 值跟踪已访问的字符。

步骤 6： 对于索引 j 处的每个字符

如果 visited[s.charAt(j)] 为 true，表示该字符已被访问，则中断内部循环。
将 visited[s.charAt(j)] 设为 true，将该字符标记为已访问。

步骤 7： 如果子串是唯一的（没有重复字符），则计算子串的长度 (j - i + 1)。

步骤 8： 使用其当前值和计算出的长度的最大值来更新 maxLength。

实施

文件名： LongestSubstring2.java

import java.io.*;
import java.util.*;

public class LongestSubstring2 {

    //Method to find the length of the longest substring without repeating characters
    public static int lengthOfLongestSubstring(String s) {
        int n = s.length(); // Get the length of the input string
        int maxLength = 0; // Initialize the maximum length

        // Use two pointers for the sliding window approach
        for (int i = 0; i < n; i++) {
            boolean[] visited = new boolean[256]; // To keep track of visited characters using ASCII values

            for (int j = i; j < n; j++) {
                // If the character is repeated, break the loop
                if (visited[s.charAt(j)]) {
                    break;
                }

                // Mark the character as visited
                visited[s.charAt(j)] = true;

                // Update the maximum length of the substring without repeating characters
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }

        return maxLength; // Return the final maximum length
    }

    public static void main(String[] args) {
        String input = "javatpoint"; // Example input string
        int result = lengthOfLongestSubstring(input); // Calculate the length of the longest substring without repeating characters

        System.out.println("Length of the longest substring without repeating characters: " + result); // Display the result
    }
}

输出

Length of the longest substring without repeating characters: 7

时间复杂度： 所提供代码的时间复杂度为 O(n2)，其中 'n' 是输入字符串的长度。这是因为代码使用了嵌套循环。外层循环运行 'n' 次，对于外层循环的每次迭代，内层循环最多运行 'n' 次。

辅助空间： 辅助空间复杂度为 O(1) 或常数空间。

方法：使用二分查找顶部

二分查找方法就像一种在有序列表中查找事物的智能方法。在查找最长无重复字符子串的长度时，它可以帮助更快地搜索最佳长度。

算法

步骤 1： 初始化代码中的变量。将输入字符串 s 的长度设为 n，并将变量 low 设为 1，high 设为 n，result 设为 0。

步骤 2： 当 low 小于或等于 high 时，执行以下操作

计算中间索引 mid = (low + high) / 2。

步骤 3： 初始化一个空集 set，用于跟踪当前窗口中的字符。

初始化 start 为 0。
通过 ends 从 0 到 n - 1 遍历输入字符串，并对每个字符执行以下操作

步骤 4： 当当前 end 处的字符违反唯一性（存在于 set 中）时

删除 start 处的字符以保持唯一性。
将 start 指针向右移动。

步骤 5： 将当前字符添加到 set 中。

检查是否满足长度条件 (end - start + 1 >= length)。
如果满足，则返回 true。

步骤 6： 如果存在长度为 mid 的子串且无重复字符（isValid 返回 true），则执行以下操作

将 result 更新为 mid。
通过设置 low = mid + 1 来调整查找更长子串的搜索空间。

步骤 7： 如果不存在长度为 mid 的子串，则执行以下操作

通过设置 high = mid - 1 来调整查找更短子串的搜索空间。

步骤 8： 二分查找完成后，返回 result 的最终值，即最长无重复字符子串的长度。

实施

文件名： BinarySearchLongestSubstring.java

import java.util.Set;
import java.util.HashSet;

public class BinarySearchLongestSubstring {

    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();

        // Binary search on the answer
        int low = 1, high = n, result = 0;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (isValid(s, mid)) {
                // If a substring of length mid is possible, search for a longer substring
                result = mid;
                low = mid + 1;
            } else {
                // If a substring of length mid is not possible, search for a shorter substring
                high = mid - 1;
            }
        }

        return result;
    }

    private static boolean isValid(String s, int length) {
        Set<Character> set = new HashSet<>();
        int start = 0;

        for (int end = 0; end < s.length(); end++) {
            // Check if adding the character at the current end violates uniqueness
            while (set.contains(s.charAt(end))) {
                // Remove the character at the start to maintain uniqueness
                set.remove(s.charAt(start));
                start++;
            }

            // Add the current character to the set
            set.add(s.charAt(end));

            // Check if the length condition is met
            if (end - start + 1 >= length) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        String input = "javatpoint";
        int result = lengthOfLongestSubstring(input);

        System.out.println("Length of the longest substring without repeating characters: " + result);
    }
}

输出

Length of the longest substring without repeating characters: 7

时间复杂度： 代码的时间复杂度为 O(n log n)，其中 "n" 是输入字符串的长度。

辅助空间： 辅助空间复杂度为 O(n)，其中 "n" 是输入字符串的长度。

方法：使用滑动窗口

通过使用滑动窗口方法，我们可以有效地探索不同的子串来找到最长的无重复字符的子串。

算法

步骤 1： 如果输入字符串长度为 0，则返回 0（没有字符需要处理）。

如果输入字符串长度为 1，则返回 1（单个字符是唯一的）。

步骤 2： 初始化最大长度 (maxLength) 为 0。

创建一个大小为 256 的布尔数组 visited，用于跟踪已访问的字符。

步骤 3： 初始化两个指针 leftPointer 和 rightPointer，都设为 0。

使用 rightPointer 遍历输入字符串。

步骤 4： 如果 rightPointer 处的字符已被访问

移动 leftPointer 向右，同时将已访问的字符标记为 false，直到重复字符不再是当前窗口的一部分。
将 rightPointer 处的字符标记为已访问。
计算当前窗口的长度 (rightPointer - leftPointer + 1)。
使用最大长度更新 maxLength。

步骤 5： 变量 maxLength 现在存储了最长无重复字符子串的长度。

步骤 6： 显示结果。

实施

文件名： SlidingWindowLongestSubstring.java

import java.io.*;

public class SlidingWindowLongestSubstring {
    public static int findLengthOfLongestSubstring(String input) {
        // If the input string length is 0
        if (input.length() == 0)
            return 0;

        // If the input string length is 1
        if (input.length() == 1)
            return 1;

        // If the input string length is more than 1
        int maxLength = 0;
        boolean[] visited = new boolean[256];

        // Pointers for the sliding window
        int leftPointer = 0, rightPointer = 0;
        while (rightPointer < input.length()) {
            // If the character at 'rightPointer' is visited
            if (visited[input.charAt(rightPointer)]) {
                // Move the 'leftPointer' to the right while marking visited characters as false until
                //The repeating character is no longer part of the current window.
                while (visited[input.charAt(rightPointer)]) {
                    visited[input.charAt(leftPointer)] = false;
                    leftPointer++;
                }
            }

            visited[input.charAt(rightPointer)] = true;

            // Calculate the length of the current window (rightPointer - leftPointer + 1)
            // and update the answer accordingly.
            maxLength = Math.max(maxLength, (rightPointer - leftPointer + 1));
            rightPointer++;
        }
        return maxLength;
    }

    // Driver code
    public static void main(String[] args) {
        // Given input string
        String inputString = "javatpoint";
        System.out.println("Given Input String: " + inputString);

        // Call the Method to find the length of the longest substring without repeating characters
        int result = findLengthOfLongestSubstring(inputString);

        // Display the result
        System.out.println("Length of the Longest Substring without repeating characters: " + result);
    }
}

输出

Given Input String: javatpoint
Length of the Longest Substring without repeating characters: 7

时间复杂度： 所提供代码的时间复杂度为 O(N)，其中 N 是输入字符串的长度。

辅助空间复杂度： 辅助空间复杂度为 O(1)，因为使用的额外空间与输入大小无关。

方法：存储每个字符的最后索引

索引存储方法涉及跟踪文本中每个字符出现的最后索引。这有助于有效地确定最长无重复字符子串的长度。

算法

步骤 1： 将输入字符串 s 的长度初始化为 n。

步骤 2： 创建一个大小为 256 的数组 lastIndex，用于存储每个字符的最后索引，所有字符都初始化为 -1。

将 maxLength 初始化为 0，用于存储最长无重复字符子串的长度。
将 start 初始化为 0，用于标记当前子串的开始。

步骤 3： 开始使用滑动窗口方法遍历输入字符串的字符。

步骤 4： 将 end 指针设置为初始位置，从 0 开始并向输入字符串的末尾 (n-1) 移动。

步骤 5： 对于在当前 end 索引处遇到的每个字符：检查字符是否已存在

检查当前子串中是否已存在该字符
条件由比较当前 end 索引处的字符的 lastIndex 与 start 指针来确定。

步骤 6： 如果当前子串中已存在该字符

将 start 指针更新为该字符最后出现位置之后的下一个索引。
这确保了滑动窗口保持唯一性，并且子串不包含重复字符。

步骤 7： 将当前字符的 lastIndex 更新为 end 索引。

这会跟踪滑动窗口内每个字符的最近出现。

步骤 8： 通过将其与当前子串的长度进行比较来更新 maxLength：这确保了 maxLength 始终存储最长无重复字符子串的长度。

步骤 9： 迭代完成后，返回 maxLength 的最终值，即最长无重复字符子串的长度。

实施

文件名： LastIndexLongestSubstring.java

import java.util.Arrays;

public class LastIndexLongestSubstring {

    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();

        // Array to store the last index of each character
        int[] lastIndex = new int[256];
        Arrays.fill(lastIndex, -1);

        int maxLength = 0;
        int start = 0; // Start of the current substring

        for (int end = 0; end < n; end++) {
            // If the character is already in the substring, update the start pointer
            start = Math.max(start, lastIndex[s.charAt(end)] + 1);

            // Update the last index of the character
            lastIndex[s.charAt(end)] = end;

            // Update the maximum length of the substring without repeating characters
            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String input = "javatpoint";
        int result = lengthOfLongestSubstring(input);

        System.out.println("Length of the longest substring without repeating characters: " + result);
    }
}

输出

Length of the longest substring without repeating characters: 7

时间复杂度： 所提供代码的时间复杂度为 O(n)，其中 'n' 是输入字符串的长度。

辅助空间： 辅助空间复杂度为 O(1)。

下一个主题Java 内部类的优点

Java 中不重复字符的最长子串长度

方法：使用滑动窗口，时间复杂度 O(n3)。

算法

实施

方法：使用滑动窗口，时间复杂度 O(n2)

算法

实施

方法：使用二分查找顶部

算法

实施

方法：使用滑动窗口

算法

实施

方法：存储每个字符的最后索引

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中不重复字符的最长子串长度

方法：使用滑动窗口，时间复杂度 O(n3)。

算法

实施

方法：使用滑动窗口，时间复杂度 O(n2)

算法

实施

方法：使用二分查找 顶部

算法

实施

方法：使用滑动窗口

算法

实施

方法：存储每个字符的最后索引

算法

实施

相关帖子

Java 驱动类

Grepcode java.util.Date

Java 和 .Net 的区别

Java.lang.outofmemoryerror: java heap space

CollationElementIterator previous() method in Java with Examples

Java 中的 Duration minusMinutes(long) 方法及示例

Java 中的静态方法

Transitive Closure of a Graph in Java

Java 中的控制台

Java Program to Find Smallest of Three Numbers Using Ternary Operator

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器

方法：使用二分查找顶部