String Encoding, Reversal, and Palindromes
Implement in-place word reversal, run-length encoding, and palindrome detection including the expand-around-centre technique.
Reversing a String In-Place
Python strings are immutable, so 'in-place' reversal means converting to a character list, swapping with two pointers, and joining. The classic two-pointer swap: place left at index 0 and right at the last index; swap characters and move pointers inward until they cross. This is O(n) time and O(n) space for the char list (irreducible since strings are immutable).
def reverse_string(s):
chars = list(s)
left, right = 0, len(chars) - 1
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1
return ''.join(chars)
print(reverse_string('hello')) # 'olleh'
print(reverse_string('Hannah')) # 'hannaH'
# Pythonic shortcut (creates new string):
print('hello'[::-1]) # 'olleh'Reversing Words in a Sentence
Reverse the order of words while trimming extra spaces. The clean Python solution: split (handles multiple spaces), reverse the list, join. For in-place reversal on a character array: reverse the whole array, then reverse each individual word. This two-pass approach runs in O(n) time with O(n) space (unavoidable with Python strings since they are immutable).
def reverse_words(s):
words = s.split() # split and strip whitespace
words.reverse() # in-place reverse
return ' '.join(words) # single space between words
print(reverse_words(' hello world ')) # 'world hello'
print(reverse_words('a good example')) # 'example good a'
# One-liner:
print(' '.join(' hello world '.split()[::-1]))All lessons in this course
- Python String API for Interviews
- Sliding Window for Substrings
- Anagrams and Character Frequency Maps
- String Encoding, Reversal, and Palindromes