Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Longest Nice Substring
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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. Fo example "AaBbB" is a nice string as A and a present, and B and b present.

If there are multiple, return the substring of the earliest occurrence. 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: ""
    • Justification: There is no contiguous substring where each character exists in both its uppercase and lowercase forms.

  3. Example 3:

    • Input: "qQwWeErR"
    • Expected Output: "qQwWeErR"
    • Justification: The entire string is the longest nice substring since every letter exists in both uppercase and lowercase forms.

Constraints:

  • 1 <= str.length <= 100
  • str consists of uppercase and lowercase English letters.

Solution

To solve the "Longest Nice Substring" problem, we utilize a divide and conquer strategy. The core idea is to identify characters in the string that do not satisfy the "nice" condition—specifically, characters that do not have both their uppercase and lowercase counterparts present in the string. By iterating through the string, we locate the first such character and use it as a delimiter to split the string into two substrings: one to the left of the offending character and one to the right. This splitting ensures that any valid "nice" substring must lie entirely within one of these two segments, as the delimiter itself cannot be part of a "nice" substring.

Once the string is split, the algorithm recursively applies the same process to each of the resulting substrings. This recursive decomposition continues until all substrings are either "nice" or empty. During each recursive call, the algorithm compares the lengths of the "nice" substrings obtained from the left and right segments and returns the longer one. If no "nice" substring is found in any segment, an empty string is returned. This approach guarantees that the longest possible "nice" substring is identified by systematically eliminating invalid characters and exploring all potential valid segments.

Step-by-Step Algorithm:

  1. Base Condition:

    • If the input string str has fewer than 2 characters, return an empty string.
      • This step is required as "nice" substring requires each character to have both uppercase and lowercase forms, which is impossible with fewer than 2 characters.

  2. Check for Nice Substring and Divide if Not Nice:

    • Convert the string str to a character array arr.

    • Create a set set containing all characters in arr. It allows quick checks for the presence of both uppercase and lowercase characters.

    • Iterate through each character c in arr:

      • If both the uppercase and lowercase forms of c are present in set, continue to the next character.
      • Else, split the string at the current index i into:
        • If a non-nice character is found, split the string into two parts: left (sub1) and right (sub2), excluding the offending character.
        • sub1 = str.substring(0, i) (left part)
        • sub2 = str.substring(i + 1) (right part)

      a. Conquer:

      • Recursively call findLongestNiceSubstring on sub1 and sub2 to find the longest nice substrings in each part.
      • This step breaks down the problem into smaller subproblems, making it easier to find the longest nice substring.

      b. Combine and Return:

      • Compare the lengths of the substrings returned from sub1 and sub2.
      • Return the longer substring, as we need to ensure that the overall longest nice substring is selected.

  3. Return the Entire String if Nice:

    • If all characters in the string satisfy the "nice" condition after the loop, return the entire string str.

Algorithm walkthrough

We will walk through the algorithm with the input string str = "BbCcXxy".

  1. Initial Call:

    • Method: findLongestNiceSubstring("BbCcXxy")
    • Input String: "BbCcXxy"

  2. Check Base Condition:

    • The string length is 7, which is greater than 2. Proceed to the next steps.

  3. Create Character Set:

    • Character Array: ['B', 'b', 'C', 'c', 'X', 'x', 'y']
    • Character Set: {B, b, C, c, X, x, y}

  4. Iterate Through Characters:

    • Index 0, Character 'B':
      • Both 'B' (uppercase) and 'b' (lowercase) are in the set. Continue.
    • Index 1, Character 'b':
      • Both 'B' and 'b' are in the set. Continue.
    • Index 2, Character 'C':
      • Both 'C' and 'c' are in the set. Continue.
    • Index 3, Character 'c':
      • Both 'C' and 'c' are in the set. Continue.
    • Index 4, Character 'X':
      • Both 'X' and 'x' are in the set. Continue.
    • Index 5, Character 'x':
      • Both 'X' and 'x' are in the set. Continue.
    • Index 6, Character 'y':
      • 'y' is present, but 'Y' is not in the set.
      • Reason: 'y' does not have its uppercase counterpart, violating the "nice" condition.

  5. Split the String:

    • Left Substring (sub1): "BbCcXx"
    • Right Substring (sub2): "" (empty)
      • Reason: The character 'y' violates the "nice" condition, so the longest nice substring must lie in sub1 or sub2.

  6. First Recursive Call (findLongestNiceSubstring("BbCcXx")):

    • Input String: "BbCcXx"

  7. Check Base Condition:

    • The string length is 6, which is greater than 2. Proceed to the next steps.

  8. Create Character Set:

    • Character Array: ['B', 'b', 'C', 'c', 'X', 'x']
    • Character Set: {B, b, C, c, X, x}

  9. Iterate Through Characters:

    • Index 0, Character 'B':
      • Both 'B' and 'b' are in the set. Continue.
    • Index 1, Character 'b':
      • Both 'B' and 'b' are in the set. Continue.
    • Index 2, Character 'C':
      • Both 'C' and 'c' are in the set. Continue.
    • Index 3, Character 'c':
      • Both 'C' and 'c' are in the set. Continue.
    • Index 4, Character 'X':
      • Both 'X' and 'x' are in the set. Continue.
    • Index 5, Character 'x':
      • Both 'X' and 'x' are in the set. Continue.
    • End of String:
      • All characters satisfy the "nice" condition.

  10. Return the Entire Substring:

    • Since all characters are nice, return "BbCcXx".
      • Reason: The whole string satisfies the "nice" condition and is the longest possible.

  11. Compare Substrings:

    • sub1 = "BbCcXx"
    • sub2 = ""
    • Longest Substring: "BbCcXx" is longer than "".

Final Output

The longest nice substring of "BbCcXxy" is "BbCcXx".

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

The time complexity of the algorithm is driven by two factors: the recursion depth and the work performed at each recursion level.

  1. Recursion Depth:

    • At each recursive step, the string is split into two parts based on the first character that violates the "nice" condition.
    • In the worst case, the string is split character by character, leading to a recursion depth of O(n), where (n) is the length of the input string.

  2. Work at Each Recursion Level:

    • At each recursive step, we:
      • Convert the string to a character array: O(n).
      • Create a set of all characters: O(n).
      • Loop through the characters in the string to check if each character is "nice": O(n).
    • Therefore, the work at each recursion level is O(n).

  3. Total Work:

    • In the worst case, there are (n) recursive levels, and each level involves O(n) work.
    • This results in a total time complexity of O(n^2).

Worst-Case Scenario Example:

  • Input: "aBcDeFgHiJkL"
    • Every character in the string is "not nice" because its counterpart (uppercase or lowercase) does not exist. The string will be split character by character, leading to O(n^2) recursive calls and work.

Space Complexity

The space complexity is determined by:

  1. Recursion Call Stack:

    • The recursion depth can reach up to (n) in the worst case.
    • Each recursive call adds a new frame to the stack, resulting in O(n) space usage.

  2. Set Storage:

    • At each recursion level, a set is created to store all unique characters in the current substring.
    • The size of the set is proportional to the length of the substring, which can be at most (n) for the first call. As the recursion progresses, the substring size decreases.
    • However, only one set exists at a time per recursion level, so this adds O(n) space.

  3. Substring Storage:

    • The method str.substring(start, end) creates new substrings at each recursive step. In the worst case, this results in O(n^2) additional memory because a new substring is created at each step.

Total Space Complexity:

  • The overall space complexity is dominated by the substring storage and recursion stack.
  • Therefore, the space complexity is O(n^2) in the worst case.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible