🔤 String Manipulation

Beginner to Intermediate ~12 min read

You're validating user input - checking if a phrase is a palindrome, ignoring spaces and punctuation. String problems are everywhere in interviews. Let's master the essential patterns.

String Fundamentals

Strings are immutable in most languages - you can't change them in place. This affects how you solve problems.

Immutability

s = "hello"
s[0] = 'H'  # Error! Can't modify

# Create new string instead
s = 'H' + s[1:]  # "Hello"

Impact: String concatenation in loops is O(n²) because each concatenation creates a new string!

Solution: Use a list/array and join at the end.

# String Manipulation Basics
# Essential string operations and patterns

print("=== String Basics ===\n")

# Strings are immutable in Python
s = "Hello"
print(f"Original: '{s}'")
# s[0] = 'h'  # Error! Can't modify

# Create new string instead
s = s.lower()
print(f"Lowercase: '{s}'\n")

print("=== Common Operations ===\n")

text = "  Python Programming  "

# 1. Strip whitespace
print(f"Original: '{text}'")
print(f"Stripped: '{text.strip()}'\n")

# 2. Split and join
words = "hello,world,python".split(',')
print(f"Split: {words}")
print(f"Join: {'-'.join(words)}\n")

# 3. Replace
message = "I love Java"
print(f"Original: {message}")
print(f"Replace: {message.replace('Java', 'Python')}\n")

print("=== Pattern: Reverse a String ===\n")

def reverse_string(s):
    """Two pointers approach"""
    chars = list(s)  # Convert to list (mutable)
    left, right = 0, len(chars) - 1
    
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    
    return ''.join(chars)

s = "hello"
print(f"Original: '{s}'")
print(f"Reversed: '{reverse_string(s)}'\n")

print("=== Pattern: Check Palindrome ===\n")

def is_palindrome(s):
    """Two pointers from both ends"""
    left, right = 0, len(s) - 1
    
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    
    return True

test_cases = ["racecar", "hello", "madam"]
for word in test_cases:
    result = "✅" if is_palindrome(word) else "❌"
    print(f"{result} '{word}' is palindrome: {is_palindrome(word)}")

print("\n=== Pattern: Character Frequency ===\n")

def char_frequency(s):
    """Count character occurrences"""
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    return freq

s = "programming"
freq = char_frequency(s)
print(f"String: '{s}'")
print(f"Frequency: {freq}\n")

print("=== Pattern: Anagram Check ===\n")

def are_anagrams(s1, s2):
    """Two strings are anagrams if they have same characters"""
    if len(s1) != len(s2):
        return False
    return sorted(s1) == sorted(s2)

pairs = [("listen", "silent"), ("hello", "world")]
for s1, s2 in pairs:
    result = "✅" if are_anagrams(s1, s2) else "❌"
    print(f"{result} '{s1}' and '{s2}': {are_anagrams(s1, s2)}")

print("\n=== Key Takeaways ===")
print("✅ Strings are immutable - create new strings")
print("✅ Use two pointers for reversal/palindrome")
print("✅ Use hash maps for frequency/anagrams")
print("✅ Sliding window for substring problems")

Output

Click Run to execute your code

Quick Quiz

Why is string concatenation in a loop slow?

Show answer
Because strings are immutable, each concatenation creates a new string and copies all characters. For n concatenations, that's 1+2+3+...+n = O(n²) operations!
How do you efficiently build a string?

Show answer
Use a list to collect parts, then join once at the end: ''.join(parts) - this is O(n) instead of O(n²).

Five Essential Patterns

# String Patterns for Interviews
# Common string problems and solutions

print("=== Pattern 1: Valid Palindrome (Ignore Non-Alphanumeric) ===\n")

def is_valid_palindrome(s):
    """Check if string is palindrome, ignoring non-alphanumeric"""
    # Filter and lowercase
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    
    # Two pointers
    left, right = 0, len(cleaned) - 1
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1
    
    return True

test = "A man, a plan, a canal: Panama"
print(f"String: '{test}'")
print(f"Valid palindrome: {is_valid_palindrome(test)} ✅\n")

print("=== Pattern 2: First Unique Character ===\n")

def first_unique_char(s):
    """Find index of first non-repeating character"""
    freq = {}
    
    # Count frequencies
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    
    # Find first with count 1
    for i, char in enumerate(s):
        if freq[char] == 1:
            return i
    
    return -1

s = "leetcode"
index = first_unique_char(s)
print(f"String: '{s}'")
print(f"First unique char at index {index}: '{s[index]}'\n")

print("=== Pattern 3: Longest Common Prefix ===\n")

def longest_common_prefix(strs):
    """Find longest common prefix among strings"""
    if not strs:
        return ""
    
    # Start with first string
    prefix = strs[0]
    
    for s in strs[1:]:
        # Shrink prefix until it matches
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    
    return prefix

words = ["flower", "flow", "flight"]
print(f"Words: {words}")
print(f"Common prefix: '{longest_common_prefix(words)}'\n")

print("=== Pattern 4: String Compression ===\n")

def compress_string(s):
    """Compress: 'aaabbc' -> 'a3b2c1'"""
    if not s:
        return ""
    
    compressed = []
    count = 1
    
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            count += 1
        else:
            compressed.append(s[i-1] + str(count))
            count = 1
    
    # Don't forget last group
    compressed.append(s[-1] + str(count))
    
    result = ''.join(compressed)
    # Return original if compression doesn't help
    return result if len(result) < len(s) else s

s = "aaabbc"
print(f"Original: '{s}'")
print(f"Compressed: '{compress_string(s)}'\n")

print("=== Pattern 5: Substring Search (Naive) ===\n")

def find_substring(text, pattern):
    """Find first occurrence of pattern in text"""
    n, m = len(text), len(pattern)
    
    for i in range(n - m + 1):
        if text[i:i+m] == pattern:
            return i
    
    return -1

text = "hello world"
pattern = "wor"
index = find_substring(text, pattern)
print(f"Text: '{text}'")
print(f"Pattern: '{pattern}'")
print(f"Found at index: {index}\n")

print("=== Interview Patterns Summary ===")
print("1. Two Pointers: Palindrome, reverse")
print("2. Hash Map: Frequency, anagrams, unique chars")
print("3. Sliding Window: Longest/shortest substring")
print("4. String Building: Compression, manipulation")
print("5. Pattern Matching: Substring search")

Output

Click Run to execute your code

Pattern	Technique	Complexity	Example
Two Pointers	Work from both ends	O(n)	Palindrome, reverse
Hash Map	Count frequencies	O(n)	Anagrams, unique chars
Sliding Window	Variable substring	O(n)	Longest substring
String Building	List + join	O(n)	Compression, reversal
Pattern Matching	Substring search	O(n×m)	Find substring

Pattern Selection Guide

Choose Your Pattern

Palindrome/Reverse: Two pointers
Anagram/Frequency: Hash map
Longest/Shortest substring: Sliding window
Build/Modify string: List + join
Find pattern: Built-in search or KMP (advanced)

Common Mistakes

❌ String Concatenation in Loop

# Slow: O(n²)
result = ""
for char in s:
    result += char  # Creates new string each time!

# Fast: O(n)
result = ''.join(s)

❌ Forgetting to Handle Empty Strings

def first_char(s):
    return s[0]  # Error if s is empty!

# Better
def first_char(s):
    return s[0] if s else None

❌ Case Sensitivity Issues

# "Hello" != "hello"
# Always normalize case first
s1.lower() == s2.lower()

Summary

The 3-Point String Guide

Immutability: Strings can't be modified - use list + join for building
Patterns: Two pointers, hash map, sliding window - same as arrays!
Efficiency: Avoid concatenation in loops - it's O(n²)

Interview tip: Most string problems use the same patterns as array problems. Think: "How would I solve this with an array?"

What's Next?

🎉 Congratulations! You've completed Module 2: Arrays & Strings!

You Now Know:

✅ Array fundamentals and O(1) access
✅ Two pointers technique
✅ Sliding window pattern
✅ String manipulation

These patterns solve 50%+ of interview array/string problems!

Next up: Module 3: Linked Lists - learn pointer-based data structures and solve problems like reversing lists, detecting cycles, and more!

Practice: Try "Valid Anagram", "Longest Substring Without Repeating Characters", and "String Compression" on LeetCode!

Previous Sliding Window

Next Bubble Sort