String Encoding, Reversal, and Palindromes
Implement in-place word reversal, run-length encoding, and palindrome detection including the expand-around-centre technique.
String Encoding, Reversal, and Palindromes is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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]))Palindrome Detection: Simple
A string is a palindrome if it equals its reverse. The fastest Python check: s == s[::-1]. For case-insensitive alphanumeric-only palindromes (the most common interview variant), normalise the string first: filter non-alphanumeric characters and convert to lowercase, then compare. Both approaches are O(n).
def is_palindrome(s):
# Filter and normalise
cleaned = ''.join(c.lower() for c in s if c.isalnum())
return cleaned == cleaned[::-1]
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # False
print(is_palindrome('Was it a car or a cat I saw?')) # TruePalindrome Detection: Two Pointers
For O(1) extra space, check palindrome with two pointers rather than slicing. Place left at 0 and right at the end. Skip non-alphanumeric characters, compare the remaining characters case-insensitively, and return False on mismatch. This is more verbose but avoids creating the cleaned string entirely — important when memory is constrained.
def is_palindrome_twoptr(s):
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1; right -= 1
return True
print(is_palindrome_twoptr('A man, a plan, a canal: Panama')) # TrueExpand Around Centre for Longest Palindrome
The expand-around-centre technique finds the longest palindromic substring in O(n²) time with O(1) extra space. For each character (odd-length palindromes) and each gap between characters (even-length palindromes), expand outward while the characters match. Track the best (start, end) pair seen. There are 2n-1 centres and each expansion is O(n) worst case.
def longest_palindrome(s):
best_start = best_end = 0
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1; right += 1
return left + 1, right - 1 # last valid bounds
for i in range(len(s)):
l, r = expand(i, i) # odd-length
if r - l > best_end - best_start:
best_start, best_end = l, r
l, r = expand(i, i + 1) # even-length
if r - l > best_end - best_start:
best_start, best_end = l, r
return s[best_start:best_end+1]
print(longest_palindrome('babad')) # 'bab' or 'aba'
print(longest_palindrome('cbbd')) # 'bb'Manacher's Algorithm Preview
Manacher's algorithm finds the longest palindromic substring in O(n) time using the insight that a palindrome inside a larger palindrome can be initialised from a mirror position. It is rarely asked to implement in interviews but is worth knowing exists. Most interviewers accept the O(n²) expand-around-centre approach as 'optimal enough' — mention Manacher's as the theoretical O(n) solution if asked for a follow-up.
# Manacher's: O(n) longest palindromic substring
def manacher(s):
# Transform s into '#a#b#a#' to handle even/odd uniformly
t = '#' + '#'.join(s) + '#'
n = len(t)
P = [0] * n # P[i] = palindrome radius at i
center = right = 0
for i in range(n):
mirror = 2 * center - i
if i < right:
P[i] = min(right - i, P[mirror])
while (i + P[i] + 1 < n and i - P[i] - 1 >= 0
and t[i+P[i]+1] == t[i-P[i]-1]):
P[i] += 1
if i + P[i] > right:
center, right = i, i + P[i]
max_len = max(P)
center_idx = P.index(max_len)
start = (center_idx - max_len) // 2
return s[start:start+max_len]
print(manacher('babad')) # 'bab'Run-Length Encoding
Run-length encoding (RLE) compresses consecutive repeated characters: 'aaabbc' becomes 'a3b2c1'. Implementation: scan with a fast pointer to find the end of each run, write the character and count to an output list, then join. The input may be shorter than the encoded output for short runs — always check if the encoded version is shorter before returning it.
def encode_rle(s):
if not s: return ''
parts = []
i = 0
while i < len(s):
char = s[i]
j = i
while j < len(s) and s[j] == char:
j += 1
count = j - i
parts.append(char + (str(count) if count > 1 else ''))
i = j
encoded = ''.join(parts)
return encoded if len(encoded) < len(s) else s
print(encode_rle('aaabbc')) # 'a3b2c'
print(encode_rle('abc')) # 'abc' (no compression gain)Decoding Run-Length Encoded Strings
Decoding RLE reads characters and following digit sequences, expanding each run. Interviewers sometimes present the LeetCode variant where the encoding uses k[encoded_string] for repeated substrings: e.g. 3[ab] → ababab. This nested variant requires a stack to handle multiple levels of nesting.
def decode_rle(s):
result = []
i = 0
while i < len(s):
char = s[i]; i += 1
num_str = ''
while i < len(s) and s[i].isdigit():
num_str += s[i]; i += 1
count = int(num_str) if num_str else 1
result.append(char * count)
return ''.join(result)
print(decode_rle('a3b2c')) # 'aaabbc'
print(decode_rle('a2b3c1')) # 'aabbbc'
# Nested bracket decode (LeetCode 394)
def decode_bracket(s):
stack = []
for c in s:
if c != ']':
stack.append(c)
else:
chars = []
while stack[-1] != '[':
chars.append(stack.pop())
stack.pop() # remove '['
k = int(stack.pop())
stack.append(''.join(reversed(chars)) * k)
return ''.join(stack)
print(decode_bracket('3[ab]')) # 'ababab'Valid Palindrome II: One Deletion Allowed
Given a string, return True if you can make it a palindrome by deleting at most one character. Use two pointers; on the first mismatch, check if either s[left+1:right+1] or s[left:right] is a palindrome (i.e., try skipping each mismatched character). If either side is a palindrome, return True. This greedy approach works because skipping the mismatched character is the only useful action.
def valid_palindrome(s):
def is_pal(l, r):
while l < r:
if s[l] != s[r]: return False
l += 1; r -= 1
return True
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
# Try skipping either character
return is_pal(left+1, right) or is_pal(left, right-1)
left += 1; right -= 1
return True
print(valid_palindrome('aba')) # True
print(valid_palindrome('abca')) # True (delete 'c')
print(valid_palindrome('abc')) # FalsePalindrome Partitioning I
Partition a string into all substrings that are palindromes. Use backtracking: at each step, try all prefixes of the remaining string; if a prefix is a palindrome, recurse on the rest. Precompute a 2D boolean table is_pal[i][j] using interval DP to make palindrome checks O(1), reducing the overall backtracking from O(n² × 2^n) to O(n × 2^n) — acceptable since generating all partitions is exponential by nature.
def partition(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
for i in range(n):
dp[i][i] = True
for length in range(2, n+1):
for i in range(n-length+1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = length == 2 or dp[i+1][j-1]
result = []
def backtrack(start, path):
if start == n: result.append(path[:]); return
for end in range(start, n):
if dp[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
print(partition('aab')) # [['a','a','b'],['aa','b']]Shortest Palindrome: String Hashing
Find the shortest palindrome obtainable by adding characters to the front of a string. The key insight: find the longest palindromic prefix of s, then prepend the reverse of the remaining suffix. To find the longest palindromic prefix efficiently, use KMP's failure function on the string s + '#' + reverse(s). The last value of the failure function gives the length of the longest palindromic prefix.
def shortest_palindrome(s):
rev = s[::-1]
combined = s + '#' + rev # '#' prevents overlap
n = len(combined)
kmp = [0] * n
j = 0
for i in range(1, n):
while j > 0 and combined[i] != combined[j]:
j = kmp[j-1]
if combined[i] == combined[j]:
j += 1
kmp[i] = j
# kmp[-1] = length of longest palindromic prefix
to_add = rev[:len(s) - kmp[-1]]
return to_add + s
print(shortest_palindrome('aacecaaa')) # 'aaacecaaa'
print(shortest_palindrome('abcd')) # 'dcbabcd'Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: palindrome detection with two pointers is O(n) time and O(1) space — always prefer index-based checks over allocating a reversed copy when space matters, expand-around-centre finds the longest palindromic substring in O(n²) by treating each of the 2n-1 positions as a potential palindrome centre, and run-length encoding compresses consecutive runs in O(n) while decoding requires a stack for the nested bracket variant. Next up we explore bubble sort and insertion sort.
Frequently asked questions
Is the “String Encoding, Reversal, and Palindromes” lesson free?
Yes — the full text of “String Encoding, Reversal, and Palindromes” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “String Encoding, Reversal, and Palindromes”?
Implement in-place word reversal, run-length encoding, and palindrome detection including the expand-around-centre technique. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “String Encoding, Reversal, and Palindromes” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Python String API for Interviews
- Sliding Window for Substrings
- Anagrams and Character Frequency Maps
- String Encoding, Reversal, and Palindromes