Longest Harmonious Subsequence

TIP103 Unit 7 Session 2 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Hard
• ⏰ Time to complete: 30 mins
• 🛠️ Topics: Divide and Conquer, String Manipulation

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What should be returned if the input string notes is empty?
  • Return an empty string since no harmonious subsequence can exist.
• What if the input string contains only one note?
  • Return an empty string since a single note cannot form a harmonious subsequence.
• Can there be multiple valid harmonious subsequences with the same length?
  • Yes, in that case, return the one that appears first.
• Does the returned harmonious subsequence have to be contiguous in notes?
  • Yes — the result must be a contiguous slice of notes. (The problem is a renaming of the classic "longest nice substring" task, where every letter that appears in the slice must appear in both its uppercase and lowercase forms.)

HAPPY CASE
Input: notes = "YazaAay"
Output: "aAa"
Explanation: The longest contiguous harmonious substring is "aAa" (positions 3-5). Only 'a'/'A' appear in it, and both cases are present. The surrounding 'Y', 'z', and 'y' all lack their case-swapped counterparts inside any substring that contains them.

Input: notes = "Bb"
Output: "Bb"
Explanation: The entire string is harmonious because both 'B' and 'b' appear.

EDGE CASE
Input: notes = "c"
Output: ""
Explanation: A single note cannot be harmonious.

Input: notes = "aAbBcCdDeEfFgG"
Output: "aAbBcCdDeEfFgG"
Explanation: The entire string is harmonious because each note and its case-swapped version appear.

2: M-atch

Match what this problem looks like to known categories of problems, e.g., Linked List or Dynamic Programming, and strategies or patterns in those categories.

For finding a specific type of subsequence within a string, we can consider the following approaches:

• Divide and Conquer: Use a divide-and-conquer approach to recursively split the string into smaller parts and find the longest harmonious subsequence.
• Recursion: The sequence can be generated recursively by first checking if the entire string is harmonious and then breaking it down further if it is not.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

1. Base Case: If the string length is less than 2, return an empty string.
2. Check Harmonious: Check if the entire string is harmonious:
   • If true, return the string.
   • If false, split the string by removing the first character that does not have its case-swapped version present, and recursively check the left and right parts.
3. Recursion: Recursively apply the above steps to both the left and right parts of the string, and return the longer harmonious subsequence.

Recursive Implementation

Pseudocode:

1) Define a helper function `is_harmonious(phrase)`:
   * Create a set of unique notes in the phrase.
   * For each note in the set, check if its case-swapped version is also in the set.
   * Return `True` if all notes have their counterparts, otherwise `False`.

2) Define the main function `divide_and_conquer(notes)`:
   * If the length of `notes` is less than 2, return an empty string.
   * If `is_harmonious(notes)` is `True`, return `notes`.
   * Iterate through each character in `notes`:
     * If the case-swapped version of `notes[i]` is not in the string, recursively apply `divide_and_conquer` to the left and right parts, and return the longer result.
   * Return an empty string if no harmonious subsequence is found.

3) The function `longest_harmonious_subsequence(notes)` will return `divide_and_conquer(notes)`.

4: I-mplement

Implement the code to solve the algorithm.

def longest_harmonious_subsequence(notes):
    def is_harmonious(phrase):
        unique_notes = set(phrase)
        for note in unique_notes:
            if note.swapcase() not in unique_notes:
                return False
        return True

    def divide_and_conquer(notes):
        if len(notes) < 2:
            return ""
        
        if is_harmonious(notes):
            return notes
        
        for i in range(len(notes)):
            if notes[i].swapcase() not in notes:
                left_result = divide_and_conquer(notes[:i])
                right_result = divide_and_conquer(notes[i+1:])
                
                if len(left_result) >= len(right_result):
                    return left_result
                else:
                    return right_result
        
        return ""

    return divide_and_conquer(notes)

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Trace through your code with the input notes = "YazaAay":
  • is_harmonious("YazaAay") returns False because 'z' has no 'Z' counterpart.
  • The loop finds 'z' at index 2 and recurses on "Ya" (which yields "", since 'Y' has no 'y' in that slice) and "aAay".
  • Inside "aAay", 'y' at index 3 forces another split: the left half "aAa" is harmonious and is returned; the right half is empty.
  • The divide-and-conquer approach therefore returns "aAa" as the longest harmonious substring.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the length of the notes string.

• Time Complexity: The worst-case time complexity is O(2^N) due to the potential recursive splitting of the string.
• Space Complexity: The space complexity is O(N) due to the recursive call stack.