代码挑战：最长的无重复字符子串 - Java 版

傷城~ 2023-10-13 08:11 25阅读 0赞

此挑战要求您找到给定字符串中不重复字符的最长子字符串。  
输入和输出示例

Input: s = "pwwkew"
    Output: 3
    The answer is "wke", with the length of 3.

### 暴力破解 ###

解决此类问题的强力方法非常简单，并且包括嵌套循环。显然，这不是一个理想的解决方案，但是如果您需要快速生成解决方案，这可能就是它。运行后我们可以对其进行优化。

public int lengthOfLongestSubstring(String s) {
        
       int n = s.length();
    
       int res = 0;
       for(int i = 0; i < n; i++){
        
         for(int j = i; j < n; j++){
        
           if(check(s, i, j)) {
        
            res = Math.max(res, j - i + 1);
           } 
          }
         }
        return res;
    }
    
    private boolean check(String s, int start, int end) {
        
      int[] chars = new int[128];
    
      for(int i = start; i <= end; i++) {
        
        char c = s.charAt(i);
        chars[c]++;
        if (chars[c] > 1) {
        
           return false;
        }
       }
      return true;
    }

上述技术给出了O(n^3)的运行时复杂度和O(min(n,m))的空间复杂度。我认为我们可以做得更好。

### 优化 ###

有一种称为“滑动窗口”的技术，经常用于解决此类问题。它的工作原理通常是在数组上维护一个固定窗口，然后一次将窗口向前移动一个元素。当窗口移动时，算法会计算当前窗口问题的答案。在这种情况下，我们的窗口不是“固定的”，但我们使用类似的概念。我们可以使用 HashSet 来存储“窗口” \[i, j\]  
中的字符（其中最初j = i）。然后我们将索引j向右移动。如果它不在我们的 HashSet 中，我们就碰撞j向右。我们这样做，直到找到哈希集中已有的字符。现在，我们找到了最大数量的不重复的子串。在整个字符串i中保持这一点，你就会得到答案。通过使用映射来定义字符到其索引的映射，可以进一步优化这个想法。这允许我们在发现重复字符时跳过字符。

让我们看看如何在这里实现它。

public int lengthOfLongestSubstring(String s) {
        
          int ans = 0;
          // map to store character and its index
          Map<Character, Integer> map = new HashMap<>(); 
          for (int end = 0, start = 0; end < s.length(); end++) {
        
             // if it is in the map, its a duplicate
             if (map.containsKey(s.charAt(end))){
        
                // move start to new index
                start = Math.max(map.get(s.charAt(end)), start);
             }
             // not in map keep track of how long the window is
             ans = Math.max(ans, end - start + 1);
             // add char to map
             map.put(s.charAt(end), end + 1);
          }
          return ans;
       }

现在，这个速度要快得多，运行时复杂度为O(n)，空间复杂度为O(min(m,n))。

### 另一个优化 ###

在为本文做一些研究时，我发现了一个更加优化的解决方案，它对字符串输入的类型做出了一些假设。根据这篇文章，“如果我们知道字符集相当小，我们可以模仿 HashSet/HashMap 的做法，用布尔/整数数组作为直接访问表。尽管查询或插入的时间复杂度仍然是 O( 1 )，数组中的常数因子比 HashMap/HashSet 中的常数因子小。”

所以如果我们假设字符串是ASCI，我们可以使用长度为128的整数数组。

public int lengthOfLongestSubstring(String s) {
        
            Integer[] chars = new Integer[128];
    
            int left = 0;
            int right = 0;
    
            int res = 0;
            while (right < s.length()) {
        
                char r = s.charAt(right);
    
                Integer index = chars[r];
                if (index != null && index >= left && index < right) {
        
                    left = index + 1;
                }
    
                res = Math.max(res, right - left + 1);
    
                chars[r] = right;
                right++;
            }
    
            return res;
        }

从这个问题中我们可以看出，暴力破解技术解决问题可能会很慢，但是，它可以帮助我们推理问题。还引入了滑动窗口技术来减少此类问题中所需的循环。请记住，如果您在问题中听到以下内容，则可以使用滑动窗口：数组、字符串、子数组、子字符串、最大总和、最大总和、最小总和。我们还看到数据结构可以帮助我们进一步优化代码。

关注我的博客，您将在其中获得提示、技巧和挑战，以保持您的技能敏锐。