Introduction

In this blog post, we will explore how to solve the LeetCode problem "1763" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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.

Explanation

Here's a breakdown of the solution:

• Iterate through all possible substrings: Generate all substrings of the input string s.
• Check if a substring is nice: For each substring, determine if it's "nice" according to the problem definition.

• Track the longest nice substring: Keep track of the longest nice substring found so far and its starting index to handle the "earliest occurrence" requirement.

• Runtime Complexity: O(n^3), where n is the length of the string s. This is due to the nested loops for generating substrings (O(n^2)) and the is_nice check which is O(n). Storage Complexity: O(1). We use a constant amount of extra space.

Code

    def longest_nice_substring(s: str) -> str:
    """
    Finds the longest nice substring of a given string.

    A string s is nice if, for every letter of the alphabet that s contains,
    it appears both in uppercase and lowercase.

    Args:
        s: The input string.

    Returns:
        The longest nice substring of s.
    """

    def is_nice(sub: str) -> bool:
        """Checks if a string is nice."""
        chars = set(sub)
        for char in chars:
            if 'a' <= char <= 'z':
                if char.upper() not in sub:
                    return False
            elif 'A' <= char <= 'Z':
                if char.lower() not in sub:
                    return False
        return True

    longest_nice = ""
    longest_len = 0

    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            sub = s[i:j]
            if is_nice(sub):
                if len(sub) > longest_len:
                    longest_nice = sub
                    longest_len = len(sub)

    return longest_nice