This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is the 1763. Longest beautiful substring on LeetCode.

Tag: “Simulation”

A string s is called a beautiful string when it contains both uppercase and lowercase letters. For example, “abABB” is A nice string, because ‘A’ and ‘A’ appear at the same time, and ‘B’ and ‘B’ appear at the same time. However, “abA” is not a nice string because ‘b’ appears and ‘b’ doesn’t.

Given a string s, return the longest beautiful substring of S. If there are more than one answer, return the first one. If there is no beautiful substring, return an empty string.

Example 1:

Input: s = "YazaAay" Output: "aAa" Explanation: "aAa" is a nice string because the substring contains only one letter, both lowercase 'a' and uppercase 'a'. "AAa" is the longest beautiful substring.Copy the code

Example 2:

Input: s = "Bb" Output: "Bb" Explanation: "Bb" is a nice string because both 'B' and 'B' appear. The entire string is also a substring of the original string.Copy the code

Example 3:

Input: s = "c" Output: "" Explanation: There are no beautiful substrings.Copy the code

Example 4:

Input: s = "dDzeE" Output: "dD" Explanation: "dD" and "eE" are both the longest beautiful substrings. Since there are multiple beautiful substrings, return "dD" because it occurs first.Copy the code

Tip:

  • 1 <= s.length <= 100
  • The s contains only upper-case and lower-case letters.

Simple solution

Since the data range is only 100, you can do whatever you want.

For this kind of data range of questions, we try to choose simple, low error rate.

An intuitive way to do this is to enumerate the “start” and “end” of each substring and check that each character in the substring contains both lowercase and uppercase letters.

class Solution {
    public String longestNiceSubstring(String s) {
        int n = s.length();
        String ans = "";
        for (int i = 0; i < n; i++) {
            out:for (int j = i + 1; j < n; j++) {
                String sub = s.substring(i, j + 1);
                if (sub.length() > ans.length()) {
                    for (char c : sub.toCharArray()) {
                        char lo = Character.toLowerCase(c), up = Character.toUpperCase(c);
                        if (sub.indexOf(lo) < 0 || sub.indexOf(up) < 0) continueout; } ans = sub; }}}returnans; }}Copy the code
  • Time complexity: O(n3)O(n^3)O(n3)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.1763 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.