How does the sliding window work in the Longest Nice Substring problem?

The sliding window expands as you find valid characters in the substring and shrinks when an invalid character is encountered. This helps efficiently find the longest nice substring.

What is a nice string in the Longest Nice Substring problem?

A string is nice if each character in the string has both its uppercase and lowercase form present, such as 'a' and 'A' or 'b' and 'B'.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the string, because each character is processed at most twice.

Can I solve this problem using a brute force approach?

Yes, but the brute force approach would be inefficient. The sliding window technique is a more optimized solution.

How can I handle strings with no nice substrings?

If no nice substring is found, return an empty string. This is a simple edge case to check for in the solution.

#1763

Easy

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

最长的美好子字符串

当一个字符串 s 包含的每一种字母的大写和小写形式同时出现在 s 中，就称这个字符串 s 是美好字符串。比方说， "abABB" 是美好字符串，因为 'A' 和 'a' 同时出现了，且 'B' 和 'b' 也同时出现了。然而， "abA" 不是美好字符串因为 'b' 出现了，而 'B' 没有…

哈希表字符串分治位运算滑动窗口

题目描述

当一个字符串 s 包含的每一种字母的大写和小写形式同时出现在 s 中，就称这个字符串 s 是美好字符串。比方说，"abABB" 是美好字符串，因为 'A' 和 'a' 同时出现了，且 'B' 和 'b' 也同时出现了。然而，"abA" 不是美好字符串因为 'b' 出现了，而 'B' 没有出现。

给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回最早出现的一个。如果不存在美好子字符串，请你返回一个空字符串。

示例 1：

输入：s = "YazaAay"
输出："aAa"
解释："aAa" 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 'a' 和大写形式 'A' 也同时出现了。
"aAa" 是最长的美好子字符串。

示例 2：

输入：s = "Bb"
输出："Bb"
解释："Bb" 是美好字符串，因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。

示例 3：

输入：s = "c"
输出：""
解释：没有美好子字符串。

示例 4：

输入：s = "dDzeE"
输出："dD"
解释："dD" 和 "eE" 都是最长美好子字符串。
由于有多个美好子字符串，返回 "dD" ，因为它出现得最早。

提示：

1 <= s.length <= 100
s 只包含大写和小写英文字母。

lightbulb

解题思路

方法一：枚举 + 哈希表

我们可以直接枚举所有子串的起点位置 $i$ ，找到以该位置所在的字符为首字符的所有子串，用哈希表 $s$ 记录子串的所有字符。

如果子串中存在一个字母找不到对应的大写字母或者小写字母，那么不满足条件，否则取最长的且最早出现的子串。

时间复杂度 $O(n^2 \times C)$ ，空间复杂度 $O(C)$ 。其中 $n$ 为字符串 $s$ 的长度，而 $C$ 为字符集的大小。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        n = len(s)
        ans = ''
        for i in range(n):
            ss = set()
            for j in range(i, n):
                ss.add(s[j])
                if (
                    all(c.lower() in ss and c.upper() in ss for c in ss)
                    and len(ans) < j - i + 1
                ):
                    ans = s[i : j + 1]
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checks if the candidate understands the sliding window technique with dynamic state updates.
question_mark
Tests the candidate's ability to optimize brute force approaches into efficient solutions.
question_mark
Looks for a clear explanation of edge cases and handling them correctly.

warning

常见陷阱

外企场景

error
Not correctly tracking the running state of characters inside the sliding window.
error
Failing to handle edge cases, such as strings that have no nice substrings or strings of length 1.
error
Using a brute force approach without optimizing the substring search using the sliding window.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider optimizing this solution further for larger strings or varying constraints.
arrow_right_alt
Try solving the problem using a divide and conquer strategy.
arrow_right_alt
Explore the possibility of using bit manipulation for state representation.

help

常见问题

外企场景

继续练习

#1016 子串能表示从 1 到 N 数字的二进制串 #1684 统计一致字符串的数目 #1876 长度为三且各字符不同的子字符串