LeetCode 1763. Longest Nice Substring

Description

https://leetcode.com/problems/longest-nice-substring/

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.

Example 4:

Input: s = "dDzeE"
Output: "dD"
Explanation: Both "dD" and "eE" are the longest nice substrings.
As there are multiple longest nice substrings, return "dD" since it occurs earlier.

Constraints:

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

Explanation

Two pointers. One starts from the beginning of the string and the other starts from the end of the string to get substrings. If a substring has the count of upper and lowercase letters is 2 times equal to lowercase, that is a nice substring. Globally record the nice substring with the greatest length.

Python Solution

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        
        i = 0
        j = len(s)
        
        
        max_sub = ""
                
        for i in range(len(s)):            
            for j in range(len(s), 0, -1):
            
                sub = s[i:j]

                lower_counter = set(sub.lower())
                upper_lower_counter = set(sub)

                if len(upper_lower_counter) == 2 * len(lower_counter):

                    if len(sub) > len(max_sub):
                        max_sub = sub            
        
        return max_sub
  • Time Complexity: O(N^2).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.