DDSA Solutions

1763. Longest Nice Substring

EasyView on LeetCode
String
Time: O(n²)
Space: O(n)

Problem Overview

Find longest nice substring (every letter has both upper and lower case).

Intuition

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

Algorithm

  1. 1For each char in s: if uppercase present but not lowercase (or vice versa): split at this char, recurse on substrings.
  2. 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
C#
// 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?

Related Problems