Lexicographically Smallest Watchlist - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 1 Standard (Click for link to problem statements)

U-nderstand

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

• Q: What is the input to the problem?
  • A: The input is a string watchlist consisting of lowercase English letters, where each letter represents a different show.
• Q: What is the output?
  • A: The output is a palindrome string that is lexicographically the smallest possible with the minimum number of operations.
• Q: How do you determine if one string is lexicographically smaller than another?
  • A: Compare the strings character by character. The first position where they differ determines which one is smaller based on the alphabetical order of the characters.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use two pointers to compare characters from both ends of the string towards the center, making changes to ensure the string becomes a palindrome and is lexicographically smallest.

1. Convert the `watchlist` string into a list to allow modification of characters.
2. Initialize two pointers:
   * `left` starting at the beginning of the list (index 0).
   * `right` starting at the end of the list (index `len(watchlist) - 1`).
3. While `left` is less than `right`:
   1. Compare the characters at the `left` and `right` pointers.
   2. If the characters are different, replace the one that is alphabetically greater with the one that is smaller to ensure the string remains lexicographically smallest.
   3. Move the `left` pointer one step to the right and the `right` pointer one step to the left.
4. Convert the modified list back to a string.
5. Return the resulting palindrome string.

⚠️ Common Mistakes

• Not correctly identifying the lexicographically smaller character when the characters differ.
• Failing to handle cases where the string is already a palindrome.
• Misplacing pointer adjustments, leading to incorrect string modifications.

I-mplement

def make_smallest_watchlist(watchlist):
    # Convert the watchlist string to a list to make it mutable
    watchlist = list(watchlist)
    
    # Initialize two pointers
    left = 0
    right = len(watchlist) - 1
    
    # Iterate until the two pointers meet
    while left < right:
        # Compare characters at the left and right pointers
        if watchlist[left] != watchlist[right]:
            # Replace the character that is alphabetically later with the earlier one
            if watchlist[left] < watchlist[right]:
                watchlist[right] = watchlist[left]
            else:
                watchlist[left] = watchlist[right]
        
        # Move the pointers inward
        left += 1
        right -= 1
    
    # Convert the list back to a string and return it
    return ''.join(watchlist)

# Example usage
print(make_smallest_watchlist("egcfe"))  # Output: "efcfe"
print(make_smallest_watchlist("abcd"))   # Output: "abba"
print(make_smallest_watchlist("seven"))  # Output: "neven"