1763. Longest Nice Substring

Time: O(n²)

Space: O(n)

Intuition

Find longest nice substring (every letter has both upper and lower case). Recursive split at characters that don't have both cases.

Algorithm

1For each char in s: if uppercase present but not lowercase (or vice versa): split at this char, recurse on substrings.
2Return longest result from recursion.

Common Pitfalls

•Split at any character missing its case pair. Try all such split points, return longest nice substring found.

1763.cs

// Approach: Divide and conquer — split at any char whose case-complement is absent, recurse and take max.
// Time: O(n²) Space: O(n)

public class Solution
{
    public string LongestNiceSubstring(string s)
    {
        if (s.Length < 2)
            return "";

        HashSet<char> seen = new HashSet<char>(s.ToCharArray());

        for (int i = 0; i < s.Length; ++i)
            if (!seen.Contains(ToggleCase(s[i])))
            {
                string prefix = LongestNiceSubstring(s.Substring(0, i));
                string suffix = LongestNiceSubstring(s.Substring(i + 1));
                return prefix.Length >= suffix.Length ? prefix : suffix;
            }

        return s;
    }

    private char ToggleCase(char c)
    {
        return char.IsLower(c) ? char.ToUpper(c) : char.ToLower(c);
    }
}

Was this solution helpful?