29. Max Unique Substring Length in a Session

Origin: Max Unique Substring Length in a Session

Given a string of lowercase letters with sessions separated by * characters, find the maximum length of a substring with all distinct letters within any single session.

* 是分隔符，把字符串分成多个 session。每个 session 内找最长无重复字符子串，返回所有 session 中的最大值。

Example

Input: sessionString = "abcabcbb"

Output: 3

Explanation: 只有一个 session “abcabcbb”。最长无重复字符子串是 “abc”、“bca” 等，长度都是 3。

Input Format

一行字符串 sessionString。

Constraints

• 0 <= S.length <= 100000
• S[i] 是 * 或小写字母 a-z
• 每个 session 是不含 * 的最大连续子串
• session 数量最多 S.length + 1

Output Format

返回一个整数：所有 session 中最长无重复字符子串的长度。空字符串或全是 * 返回 0。

Sample Input 0

*

Sample Output 0

0

Sample Input 1

aa

Sample Output 1

1

---

函数契约

// 输入：sessionString（含 * 分隔符和小写字母的字符串）
// 输出：所有 session 中最长无重复字符子串的长度
// 边界：空字符串 → 0；全是 * → 0；单个字符 → 1

边界表

场景	返回什么
空字符串	0
全是 *	0
单个字符	1
* 开头或结尾	忽略空 session
正常	最长无重复子串长度

Resolution

解法一：滑动窗口 + Set（标准解法）

function maxDistinctSubstringLengthInSessions(sessionString: string): number {
    if (!sessionString?.length) return 0
    let left = 0;
    let maxLength = 0;
    let set = new Set()
    for (let right = 0; right < sessionString.length; right++) {
        const char = sessionString[right]
        if (char === '*') {
            set.clear()
            left = right + 1
        }
        while (set.has(char)) {
            set.delete(sessionString[left])
            left++
        }
        set.add(char)
        maxLength = Math.max(maxLength, right - left + 1)
    }
    return maxLength
}

这是我自己重新理解的版本。核心：Set 不重建，right 加字符，遇到重复从 left 删，删到没重复为止。

暴力解法（O(n²)，超时，理解思路用）

function maxDistinctSubstringLengthInSessions(sessionString: string): number {
    if (!sessionString?.length) return 0
    let maxLength = 0
    const sessions = sessionString.split('*')
    for (const session of sessions) {
        for (let i = 0; i < session.length; i++) {
            const set = new Set()
            for (let j = i; j < session.length; j++) {
                if (!set.has(session[j])) {
                    set.add(session[j])
                    maxLength = Math.max(maxLength, j - i + 1)
                } else {
                    break
                }
            }
        }
    }
    return maxLength
}

每个起点 i 往后扩展 j，遇到重复就停。先 split('*') 把 * 的处理和滑动窗口分开，每个 session 独立处理。

踩坑：外层循环写 i < session.length - 1 会跳过最后一个字符，单字符 session 返回 0 而不是 1。应该是 i < session.length。

解法二：滑动窗口 + Map（优化版）

function maxDistinctSubstringLengthInSessions(s: string): number {
    let left = 0
    let maxLength = 0
    const lastIndex = new Map<string, number>()
    for (let right = 0; right < s.length; right++) {
        const char = s[right]
        if (char === '*') {
            lastIndex.clear()
            left = right + 1
        } else {
            if (lastIndex.has(char) && lastIndex.get(char)! >= left) {
                left = lastIndex.get(char)! + 1
            }
            lastIndex.set(char, right)
            maxLength = Math.max(maxLength, right - left + 1)
        }
    }
    return maxLength
}

核心思路

怎么想出来的？ 找最长无重复子串。暴力做法每个起点扫一遍 O(n²)。但发现一个规律：如果窗口 [left, right] 里没重复，right 往右走一步，要么还没重复（窗口变长），要么有重复了。

重复了怎么办？ 把 left 往右移，把重复的那个字符挤出去。挤出去之前窗口里不会有重复，挤出去之后也不会有重复。不需要重新从头扫，left 追着 right 走就行。

为什么是 O(n)？ right 一直往右走 n 步，left 也一直往右走最多 n 步，两个指针都不回头。加起来 O(2n) = O(n)。

* 怎么处理？ * 是 session 分隔符，遇到它清空窗口，left 跳到 * 后面，相当于重新开始。不需要真的用 * 分割字符串。

关键洞察：窗口里如果有重复，重复一定在新加入的字符。所以只需要把 left 移到重复字符之后，窗口就又合法了。

两解对比

	Set 解法	Map 解法
遇到重复	while 循环一个一个删 left	直接跳到重复字符之后
复杂度	O(2n)，left 逐步走	O(n)，left 直接跳
容易理解	是	稍难，要多想一步

复杂度

• 时间：O(n)，两个指针各最多走 n 步
• 空间：O(min(m, n))，m 是字符集大小（小写字母 26 个）

参考来源

• 相关文章：算法解题流程：从读题到提交的七步