最长子串问题

问题描述

Given a string, find the length of the longest substring without repeating characters.

Examples:

  • Given “abcabcbb”, the answer is “abc”, which the length is 3.
  • Given “bbbbb”, the answer is “b”, with the length of 1.
  • Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

解题思路

  1. start记录本次字符串扫描的起始位置;i从start开始顺序扫描字符串,扫描过程中如果位置i所在的字符没有出现在start开始的子串中,则扩展当前子串数组,如下图

1

  1. 如果i所在的字符出现在start开始的子串中,那么表示当前获得了一个无重复字符的子串s[start, i),此时比较该子串与已记录的最长无重复字符的子串的长度;同时获得s[i]字符在字符串中的位置p,接下来将start游标移至紧接着p的位置处,继续下一次子串寻找过程。
    如下图:在上图中i到b位置处出现了重复字符,那上一个无重复的的子串是[a, b, c, d]。接下来,start游标可以从第一个b后面的c开始去搜寻子串了。

2

  1. 继续上面描述的扫描过程,如下图:

3

  1. 算法在i或者start扫描到字符串末尾的时候宣告结束,找到了最长子串[d, b, c, a, e].有兴趣的可以计算算法复杂度。

算法源码

func charPos(str []byte, c byte) int {
    for i, s := range str {
        if c == s {
            return i
        }
    }
    return -1
}

func lengthOfLongestSubstring(s string) int {
    var substr []byte
    longestSubStr := 0
    substrPos := 0

    for start := 0; start < len(s); {
        i := start
        for ; i < len(s); i++ {
            pos := charPos(substr, s[i])
            if pos >= 0 {
                if len(substr) > longestSubStr {
                    longestSubStr = len(substr)
                }
                substr = substr[:0]
                start = pos + 1 + substrPos
                substrPos = start
                break
            } else {
                substr = append(substr, s[i])
            }
        }
        if i == len(s) {
            break
        }
    }

    if len(substr) > longestSubStr {
        longestSubStr = len(substr)
    }
    return longestSubStr
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>