Longest Harmonious Subsequence - codepath/compsci_guides GitHub Wiki

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.
HAPPY CASE
Input: notes = "GadaAg"
Output: "aAa"
Explanation: The longest harmonious subsequence is "aAa" because both 'A' and 'a' appear.

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 = "GadaAg":
    • The divide-and-conquer approach should correctly identify "aAa" as the longest harmonious subsequence.

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.