算法-水位-无重复字符的最长子序列

阳光穿透心脏的1/2处 2023-07-20 05:48 2阅读 0赞

# 算法-水位-无重复字符的最长子序列 #

# 1 概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/longest-common-subsequence/

## 1.2 题目描述 ##

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”  
输出: 3  
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。  
示例 2:

输入: “bbbbb”  
输出: 1  
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。  
示例 3:

输入: “pwwkew”  
输出: 3  
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

**请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。**

# 2 题解 #

## 2.1 水位 ##

### 2.2.1 解题思路 ###

思路是关注最近的两个相同字符间距离，同时增加水位限制，水位始终为0或相同字符较旧那个位置的下一个位置。

水位用来限制计算重复元素的最小位置，不能低于水位去找重复元素来计算路径长度，因为水位所在的位置之前已经有其他重复元素了。

比如abca，初始为0，直到第二个a时水位更新为前一个a的下一个位置即1  
再比如 kacbak  
第一次遇到重复元素a时，将水位置为 1 + 1 = 2  
第二次，又遇到重复元素k，此时因为上次重复的k的位置0在数位2之下，表示旧k位置和水位之间有其他重复元素，这里就是a  
所以不能直接以 第二个k的位置 5 - 第一个k的位置的下一个位置 1 + 1 这样计算长度，因为存在重复元素a！

同时本算法用256位的int数组代替了HashMap，速度再次提高  
取256的原因是,char为8bit，即针最多2^8-1 个字符

### 2.2.2 代码 ###

class Solution { 
        public int lengthOfLongestSubstring(String s) { 
            // records elements` index
            int[] map = new int[256];
    
            // max substring length
            int max = 0;
            // keep the watermark next to the newly found old position
            int watermark = 0;
            // temporary count
            int tmp = 0;
    
            for(int i = 0; i < s.length(); i++){ 
                int old = map[s.charAt(i)];
                if(old == 0){ 
                    // means the element has not appeared before
                    
                    // just need to increment the tmp
                    tmp++;
                }else{ 
                    // means the element has appeared before
    
                    // need update the max
                    max = Math.max(max,tmp);
    
                    // old--: the char`s true index in the string
                    old--;
                    
                    if(old < watermark){ 
                        // the old position is lower than the watermark,
                        // just need to update the tmp
                        tmp = i - watermark + 1;  
                    } else { 
                        // the old position is not lower than the watermark, need to update 
                        // the watermark to keep the watermark next to the newly found 
                        // old position
                        watermark = old + 1;
    
                        // update the tmp
                        tmp = i - watermark + 1;  
                    }
                }
                // update the element`s position
                map[s.charAt(i)] = i+1;
            }
            return Math.max(max,tmp);
        }
    }

### 2.2.3 时间复杂度 ###

O(n)

在leetcode运行结果：  
![s][]

### 2.2.4 空间复杂度 ###

256，`O(C)`

也可以用HashMap代替int数组，只不过效率会低一些，因为可能会存在扩容、Hash冲突、链表变红黑树等操作。

[s]: /images/20230528/b7a38f5c36c14dfea50634ed6dd2261e.png