刻意练习：LeetCode实战 -- Task16. 无重复字符的最长子串

背景

本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了 三个简单、两个中等、一个困难 等级的题目，共计三十道题，利用三十天的时间完成这组刻意练习。

本次任务的知识点：字符串

字符串或串（string） 是由数字、字母、下划线组成的一串字符。一般记为 s = “a1a2...an”（n >= 0）。它是编程语言中表示文本的数据类型。

通常以串的整体作为操作对象，如：在串中查找某个子串在该串中首次出现的位置、在串的某个位置上插入一个子串以及删除一个子串等。两个字符串相等的充要条件是：长度相等，并且各个对应位置上的字符都相等。串通常以顺序的方式进行存储与实现。

---

题目

• 题号：3
• 难度：中等
• https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

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

示例 1:

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

示例 2:

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

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

---

实现

C# 语言

思路：借助动态规划的思路，从前到后求出以每个位置为终止位置，所构成无重复子串的长度，之后求这些长度的最大值即可。

对于任意位置index其最长无重复子串的长度为result[index] = min{k1,k2}，k1 = result[index-1] + 1，k2为从index位置往前推直到出现index位置的字符或index=0为止的子串长度。

• 执行结果：通过
• 执行用时：96 ms, 在所有 C# 提交中击败了 82.81% 的用户
• 内存消耗：25.2 MB, 在所有 C# 提交中击败了 25.52% 的用户

public class Solution
{
    public int LengthOfLongestSubstring(string s)
    {
        if (string.IsNullOrEmpty(s))
            return 0;
        int[] result = new int[s.Length];
        result[0] = 1;

        for (int i = 1; i < s.Length; i++)
        {
            int count = GetLength(i, s);
            result[i] = result[i-1] < count ? result[i-1]+1 : count;
        }
        return result.Max();
    }
    private int GetLength(int index,string s)
    {
        char c = s[index];
        int result = 1;
        for (int i = index-1; i >= 0; i--)
        {
            if (s[i] != c)
                result += 1;
            else
                break;
        }
        return result;
    }
}

Python 语言

• 执行结果：通过
• 执行用时：724 ms, 在所有 Python3 提交中击败了 9.22% 的用户
• 内存消耗：13.7 MB, 在所有 Python3 提交中击败了 5.01% 的用户

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0
        result = list()
        result.append(1)
        for i in range(1, len(s)):
            count = self.GetLength(i, s)
            result.append(result[i - 1] + 1 if result[i - 1] < count else count)
        return max(result)

    def GetLength(self, index: int, s: str):
        c = s[index]
        result = 1
        for i in range(index - 1, -1, -1):
            if s[i] != c:
                result += 1
            else:
                break
        return result

---

往期活动

LSGO软件技术团队会定期开展提升编程技能的刻意练习活动，希望大家能够参与进来一起刻意练习，一起学习进步！

• Python基础刻意练习活动即将开启，你参加吗？
• Task01：变量、运算符与数据类型
• Task02：条件与循环
• Task03：列表与元组
• Task04：字符串与序列
• Task05：函数与Lambda表达式
• Task06：字典与集合
• Task07：文件与文件系统
• Task08：异常处理
• Task09：else 与 with 语句
• Task10：类与对象
• Task11：魔法方法
• Task12：模块

---

我是 终身学习者“老马”，一个长期践行“结伴式学习”理念的 中年大叔。

我崇尚分享，渴望成长，于2010年创立了“LSGO软件技术团队”，并加入了国内著名的开源组织“Datawhale”，也是“[e-mail]”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。

愿我们一起学习，一起进步，相互陪伴，共同成长。

后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：