Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Longest Nice Substring (easy)

Problem Statement

Given a string str, return the longest nice substring of a given string.

A substring is considered nice if for every lowercase letter in the substring, its uppercase counterpart is also present, and vice versa.

If no such string exists, return an empty string.

Examples

  1. Example 1:

    • Input: "BbCcXxY"
    • Expected Output: "BbCcXx"
    • Justification: Here, "BbCcXx" is the longest substring where each letter's uppercase and lowercase forms are present.

  2. Example 2:

    • Input: "aZAbcD"
    • Expected Output: ""

.....

.....

.....

Like the course? Get enrolled and start learning!
J

jasonjackson42

· a year ago

  • Number of recursive calls: O(N) (there can be only as many as N splits of the given string
  • Work done per split: O(N) (due to slicing O(N) + set creation O(N) )
  • Overall worst-case complexity: O(N²)