1763. 最长的美好子字符串

🟢   🔖  位运算 哈希表 字符串 分治 滑动窗口  🔗 力扣 LeetCode

题目

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.

Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.

Example 1:

Input: s = "YazaAay"

Output: "aAa"

Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.

"aAa" is the longest nice substring.

Example 2:

Input: s = "Bb"

Output: "Bb"

Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.

Example 3:

Input: s = "c"

Output: ""

Explanation: There are no nice substrings.

Constraints:

• 1 <= s.length <= 100
• s consists of uppercase and lowercase English letters.

题目大意

当一个字符串 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 只包含大写和小写英文字母。

解题思路

可以使用分治法来解决这一问题。

• 如果当前字符串中的某个字符只存在小写或大写形式，则当前字符串不可能是优美字符串。
• 我们以该字符为分隔点，将字符串分成两个子字符串，分别递归求解最长的优美子字符串。
  • 比较两个子字符串的长度，返回较长的那个。
• 终止条件：如果字符串长度小于等于 1，则无法形成优美字符串，返回空字符串。

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是字符串的长度。
• 空间复杂度：O(n)，递归调用的深度最大为字符串长度 n。

代码

/**
 * @param {string} s
 * @return {string}
 */
var longestNiceSubstring = function (s) {
	const n = s.length;
	if (n <= 1) return ''; // 长度为 1 或 0 的字符串不能是优美字符串

	let set = new Set([...s]); // 将字符串中的字符放入集合中
	for (let i = 0; i < n; i++) {
		const c = s[i];
		// 如果当前字符的另一种大小写形式不存在，则分治处理
		if (!set.has(c.toUpperCase()) || !set.has(c.toLowerCase())) {
			const sub1 = longestNiceSubstring(s.substring(0, i)); // 左子字符串
			const sub2 = longestNiceSubstring(s.substring(i + 1)); // 右子字符串
			return sub1.length >= sub2.length ? sub1 : sub2; // 返回较长的优美子字符串
		}
	}
	return s; // 当前字符串是优美字符串，直接返回
};

相关题目

题号	标题	题解	标签	难度	力扣
2421	好路径的数目		树 并查集 图 3+	🔴	🀄️ 🔗