Longest Nice Substring - Practice Coding Problems

Longest Nice Substring - Problem

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 nice because 'b' appears lowercase, but 'B' does not appear uppercase.

Given a string s, return the longest substring of s that is nice. If there are multiple longest nice substrings, return the substring of the earliest occurrence. If there are no nice substrings, return an empty string.

Input & Output

Example 1 — Complete Nice String

$ Input: s = "abABB"

› Output: "abABB"

💡 Note: The whole string is nice because 'a' and 'A' both appear, 'b' and 'B' both appear. This is the longest (and only) nice substring.

Example 2 — Partial Nice Substring

$ Input: s = "YazaAay"

› Output: "aAa"

💡 Note: The character 'Y' appears but 'y' does not, and 'z' appears but 'Z' does not. The substring "aAa" is nice because 'a' and 'A' both appear.

Example 3 — No Nice Substring

$ Input: s = "Bb"

› Output: "Bb"

💡 Note: Both 'B' and 'b' appear, making the entire string nice. Length is 2.

Constraints

1 ≤ s.length ≤ 100
s consists of uppercase and lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Examine string "abABB" for character case pairs

Validation

Check if each character has its uppercase/lowercase partner

Result

Return the longest valid nice substring

Key Takeaway

🎯 Key Insight: A nice substring requires every character to have both its uppercase and lowercase versions present

Asked in

M Microsoft 15 a Amazon 8

The key insight is that if a character appears without its case partner, it cannot be part of any nice substring. The divide and conquer approach efficiently eliminates impossible characters by splitting the string recursively. Best time complexity: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Divide and Conquer	O(n²)	O(n)	Recursively split string at invalid characters to find nice substrings
Hash Map Character Tracking	O(n² × k)	O(k)	Use hash map to efficiently check character pairs in each substring
Brute Force - Check All Substrings	O(n³)	O(1)	Check every possible substring to see if it's nice

Divide and Conquer — Algorithm Steps

Step 1: Find all characters that don't have their case partners
Step 2: If no invalid characters, the whole string is nice
Step 3: Split at invalid characters and recursively check each part

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Invalid Chars

Identify characters without case partners

Split & Recurse

Divide string at invalid characters

Return Longest

Compare results and return the longest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

char* longestNiceSubstring(char* s, int start, int end) {
    if (end - start < 2) {
        char* empty = malloc(1);
        empty[0] = '\0';
        return empty;
    }
    
    int chars[128] = {0};
    for (int i = start; i < end; i++) {
        chars[(int)s[i]] = 1;
    }
    
    for (int i = start; i < end; i++) {
        char c = s[i];
        char partner = islower(c) ? toupper(c) : tolower(c);
        
        if (!chars[(int)partner]) {
            char* left = longestNiceSubstring(s, start, i);
            char* right = longestNiceSubstring(s, i + 1, end);
            
            if (strlen(left) >= strlen(right)) {
                free(right);
                return left;
            } else {
                free(left);
                return right;
            }
        }
    }
    
    char* result = malloc((end - start + 1) * sizeof(char));
    strncpy(result, s + start, end - start);
    result[end - start] = '\0';
    return result;
}

char* solution(char* s) {
    return longestNiceSubstring(s, 0, strlen(s));
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each recursive call processes O(n) characters, with O(n) possible recursive levels in worst case

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack can go O(n) deep, plus O(n) space for character sets

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Divide and Conquer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler