查找无重复最长子串

[编程题]查找无重复最长子串

热度指数：5892 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围：输入的字符串长度满足 $1 \le n \le 10^5 \$ ，字符串中仅包含小写的英文字母

输入描述:

输入类型为字符串，例如”abcde“

输出描述:

输出类型为整型， 例如 5

示例1

输入

pwwkew

输出

说明

无重复字符的最长子串是"kew"，其长度为 3

算法知识视频讲解

Python3

TS9527

经典双指针，左指针移动就行了，每次移动到当前字符上一次出现位置的下一个（记得取最大）

class MainActivity:

    def main(self):
        # Read the data
        s = input()
        # Initialization
        leftPtr = 0
        result = 1
        records = dict()
        # Traverse
        for rightPtr, char in enumerate(s):
            if char in records:
                leftPtr = max(leftPtr, records[char] + 1)
            records[char] = rightPtr
            result = max(result, rightPtr - leftPtr + 1)
        print(result)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-08-24 16:17:49 回复(0)