TIP102 Unit 3 Session 1 Standard (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
watchlist
consisting of lowercase English letters, where each letter represents a different show.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
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"