leetcode
leetcode 2701 ~ 2750
最长的美好子字符串

最长的美好子字符串

难度:

标签:

题目描述

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.

代码结果

运行时间: 26 ms, 内存: 16.0 MB

/*
 * 思路：
 * 1. 使用Java Stream对字符串进行处理。
 * 2. 生成所有可能的子字符串。
 * 3. 过滤出美好子字符串。
 * 4. 找到最长的美好子字符串，如果有多个，返回最早出现的。
 */
import java.util.stream.IntStream;
public class Solution {
    public String longestNiceSubstring(String s) {
        return IntStream.range(0, s.length())
            .boxed()
            .flatMap(i -> IntStream.range(i + 1, s.length() + 1)
                .mapToObj(j -> s.substring(i, j)))
            .filter(this::isNice)
            .max((a, b) -> a.length() == b.length() ? s.indexOf(a) - s.indexOf(b) : a.length() - b.length())
            .orElse("");
    }

    private boolean isNice(String s) {
        return s.chars().allMatch(c -> Character.isLowerCase(c) ? s.indexOf(Character.toUpperCase(c)) >= 0 : s.indexOf(Character.toLowerCase(c)) >= 0);
    }
}

解释

方法:

这个题解采用了递归的方式来找出最长的美好子字符串。首先，它检查整个字符串是否为美好字符串，即每个在字符串中出现的字符的大写和小写形式都必须同时存在。如果整个字符串是美好的，直接返回整个字符串。如果不是，它找到第一个不满足美好字符串条件的字符，然后将字符串分成左右两部分，在这两部分中递归地寻找最长的美好子字符串。最后，比较左右两部分得到的最长美好子字符串的长度，返回较长的那个。

时间复杂度:

O(n^2)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在检查是否为美好字符串时，仅通过字符的大写或小写形式在字符串中的存在来判断？是否有更高效的方式来验证字符的大小写形式同时存在？
▷
在检查是否为美好字符串时，通过字符的大写或小写形式在字符串中的存在来判断是一种直观的方法，因为美好字符串的定义是每个字符的大写和小写形式都必须同时存在。更高效的方法可能包括使用位运算或哈希表。例如，可以用一个位向量（整数）来跟踪哪些字母已经以大写或小写形式出现。每个字母对应位向量中的两个位，一个表示小写，一个表示大写。遍历字符串时，更新这些位，最后检查位向量中的相关位对是否都被设置，从而判断是否所有字符都满足美好字符串的条件。这种方法可能在某些情况下比逐个字符检查更快，特别是字符串很长时。
🦆
在递归过程中，如果中间的字符不满足美好字符串的条件，为什么选择忽略这个字符而直接对左右两部分进行递归？是否有可能忽略了包含该字符的更长的美好子字符串？
▷
在递归过程中忽略不满足条件的字符是基于这样的事实：如果一个字符的大小写形式不同时存在，那么包含这个字符的任何字符串都不能是美好字符串。因此，将字符串分割成不包含该字符的左右两部分，分别递归寻找各自的最长美好子字符串，是一种合理的策略。这种方法不会忽略可能的更长美好子字符串，因为任何包含不满足条件字符的子字符串本身就不能是美好的。
🦆
在递归返回最长美好子字符串的过程中，比较左右字符串长度是否足够判断最长子字符串，还是也需要考虑它们的起始位置以确保返回最早出现的一个？
▷
在这个递归方法中，主要目标是找到最长的美好子字符串，因此比较左右子字符串的长度通常是足够的。如果两个子字符串的长度相同，则由于递归的性质，先处理的（即左侧的）子字符串将被优先返回。因此，在这种情况下，不需要额外考虑它们的起始位置。只有在处理多个长度相同的最长美好子字符串时，才需要考虑返回最早出现的一个，但通常这种情况下返回任何一个都是可接受的。

相关问题

放置盒子字符串中不同整数的数目