Reverse String

What You'll Learn

In-place modification vs creating new strings.

Real-World Context

"Like flipping a cassette tape or reading a word in a mirror. 'hello' becomes 'olleh'."

Breaking It Down

Convert string to a mutable format (like a list or array)
Use two pointers: one at start, one at end
Swap characters and move pointers toward center
Join back into a string

Python 3

def reverse_string(s):
    # Python strings are immutable, so we use slicing or list
    return s[::-1]

# Two-pointer approach
def reverse_string_2p(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)

Line-by-Line Walkthrough

In Python, s[::-1] is the most efficient way. In C++, we can modify the string in-place using two pointers, which is very memory efficient.

Complexity Analysis

Time: O(N)
Space: O(N) for Python (new string), O(1) for C++ (in-place)
We visit each character once.

Common Mistakes

❌ Trying to modify a Python string directly (s[0] = 'a')
✅ Strings in Python are immutable. Convert to a list first.

Try It Yourself

Can you reverse a string without using any extra space in Python?

Palindrome String

What You'll Learn

Case sensitivity and special character handling.

Real-World Context

"A word that reads the same both ways, like 'radar' or 'madam'."

Breaking It Down

Clean the string (remove spaces, convert to lowercase)
Compare the string with its reverse
Or use two pointers to compare characters from both ends

Python 3

def is_palindrome(s):
    s = s.lower().replace(" ", "")
    return s == s[::-1]

Line-by-Line Walkthrough

The two-pointer approach is better as it doesn't require creating a reversed copy of the string, saving memory.

Complexity Analysis

Time: O(N)
Space: O(1)
We only use two pointers.

Common Mistakes

❌ Forgetting to handle uppercase/lowercase differences
✅ Always normalize the string using .lower() or tolower() before comparing.

Try It Yourself

Modify the code to ignore all non-alphanumeric characters (like punctuation).

Anagram Check

What You'll Learn

Using frequency arrays or sorting to compare content.

Real-World Context

"Two words are anagrams if they use the exact same letters, like 'listen' and 'silent'."

Breaking It Down

Check if lengths are equal
Sort both strings and compare
OR: Count frequency of each character in both strings and compare counts

Python 3

def are_anagrams(s1, s2):
    return sorted(s1) == sorted(s2)

# Frequency count approach
from collections import Counter
def are_anagrams_fast(s1, s2):
    return Counter(s1) == Counter(s2)

Line-by-Line Walkthrough

Sorting is easy to implement but takes O(N log N). Using a frequency array (size 256 for ASCII) takes O(N) and is the preferred interview solution.

Complexity Analysis

Time: O(N log N) for sorting, O(N) for frequency count
Space: O(1) if we use a fixed-size array of 256
Frequency count only needs to visit each character once.

Common Mistakes

❌ Not checking length first
✅ If lengths are different, they can't be anagrams. This is a quick O(1) exit.

Try It Yourself

How would you handle anagrams if the strings contained Unicode characters (like emojis)?

First Non-Repeating

What You'll Learn

Using a hash map or frequency array for lookups.

Real-World Context

"Finding the first character that appears only once. In 'swiss', 'w' is the first non-repeating character."

Breaking It Down

Create a frequency map of all characters
Iterate through the string again
Return the first character that has a count of 1

Python 3

def first_unique(s):
    counts = {}
    for char in s:
        counts[char] = counts.get(char, 0) + 1
    
    for char in s:
        if counts[char] == 1:
            return char
    return None

Line-by-Line Walkthrough

We need two passes: one to count everything, and one to find the first one that appeared only once. This is a classic 'trade space for time' problem.

Complexity Analysis

Time: O(N)
Space: O(1) (max 256 characters for ASCII)
We visit each character twice.

Common Mistakes

❌ Returning the first character with count 1 from the map
✅ Maps don't always preserve order. You must iterate through the original string to find the 'first' one.

Try It Yourself

Can you solve this in a single pass? (Hint: Store the index in the map)

Reverse Words

What You'll Learn

Splitting, reversing, and joining.

Real-World Context

"Turning 'Sky is blue' into 'blue is Sky'. Common in text processing apps."

Breaking It Down

Split the string into a list of words
Reverse the list of words
Join the words back with spaces

Python 3

def reverse_words(s):
    words = s.split()
    return " ".join(words[::-1])

Line-by-Line Walkthrough

In Python, this is a one-liner. In C++, we use stringstream to easily extract words, then build the result backwards.

Complexity Analysis

Time: O(N)
Space: O(N)
We store all words in a new structure.

Common Mistakes

❌ Forgetting to handle multiple spaces between words
✅ Use split() in Python or stringstream in C++ which automatically handle whitespace.

Try It Yourself

Can you reverse the words in-place without using extra space for a list/vector?

Count Vowels

What You'll Learn

Iterating and checking against a set of characters.

Real-World Context

"Counting how many a, e, i, o, u are in a sentence."

Breaking It Down

Initialize vowel and consonant counters to 0
Convert string to lowercase
Iterate through each character
If it's a vowel, increment vowel count
If it's an alphabet but not a vowel, increment consonant count

Python 3

def count_vowels_consonants(s):
    vowels = "aeiou"
    v_count = c_count = 0
    for char in s.lower():
        if char.isalpha():
            if char in vowels:
                v_count += 1
            else:
                c_count += 1
    return v_count, c_count

Line-by-Line Walkthrough

We use a simple loop and check each character. Normalizing to lowercase first simplifies the logic.

Complexity Analysis

Time: O(N)
Space: O(1)
We visit each character once.

Common Mistakes

❌ Counting spaces or numbers as consonants
✅ Always use isalpha() to ensure you're only counting letters.

Try It Yourself

Can you count the number of digits in the string as well?

Remove Spaces

What You'll Learn

String filtering and joining.

Real-World Context

"Cleaning up a string by removing all whitespace. 'a b c' becomes 'abc'."

Breaking It Down

Iterate through the string
If character is not a space, add it to the result

Python 3

def remove_spaces(s):
    return "".join(s.split())

# Alternative
def remove_spaces_manual(s):
    return s.replace(" ", "")

Line-by-Line Walkthrough

In Python, split() and join() is very efficient as it handles all types of whitespace (tabs, newlines). In C++, we build a new string character by character.

Complexity Analysis

Time: O(N)
Space: O(N)
We create a new string without spaces.

Common Mistakes

❌ Only removing the first space
✅ Use a loop or a global replace function to remove all occurrences.

Try It Yourself

Can you remove spaces in-place in C++ using the 'erase-remove' idiom?

Case Conversion

What You'll Learn

ASCII manipulation and built-in functions.

Real-World Context

"Swapping uppercase to lowercase and vice versa. 'AbC' becomes 'aBc'."

Breaking It Down

Iterate through each character
If uppercase, convert to lowercase
If lowercase, convert to uppercase

Python 3

def swap_case(s):
    return s.swapcase()

Line-by-Line Walkthrough

Most languages have built-in functions for this. Under the hood, it's often done by adding or subtracting 32 from the ASCII value of the character.

Complexity Analysis

Time: O(N)
Space: O(1) if in-place, O(N) if new string
We visit each character once.

Common Mistakes

❌ Trying to convert non-alphabetic characters
✅ Built-in functions like tolower() usually handle non-alphabetic characters by returning them unchanged.

Try It Yourself

Can you implement this using bitwise XOR with 32?

Max Occurring Char

What You'll Learn

Frequency mapping and finding the maximum.

Real-World Context

"Finding which character appears most often in a string. In 'apple', 'p' is the max occurring character."

Breaking It Down

Create a frequency map (dictionary or array)
Find the character with the highest count

Python 3

def max_char(s):
    counts = {}
    for char in s:
        counts[char] = counts.get(char, 0) + 1
    return max(counts, key=counts.get)

Line-by-Line Walkthrough

We use an array of size 256 to store counts for all possible ASCII characters. This is very fast and uses constant extra space.

Complexity Analysis

Time: O(N)
Space: O(1)
The frequency array size is fixed at 256.

Common Mistakes

❌ Not handling ties
✅ Decide if you want to return the first one found or all of them.

Try It Yourself

How would you handle this for Unicode strings with thousands of possible characters?

Only Digits Check

What You'll Learn

String validation logic.

Real-World Context

"Checking if a string contains only numbers, like a phone number or zip code."

Breaking It Down

Iterate through the string
If any character is not a digit, return False
If loop finishes, return True

Python 3

def is_only_digits(s):
    return s.isdigit()

Line-by-Line Walkthrough

A simple validation loop. In Python, .isdigit() is the standard way.

Complexity Analysis

Time: O(N)
Space: O(1)
We check each character once.

Common Mistakes

❌ Returning True for an empty string
✅ Always check if the string is empty first, as an empty string usually shouldn't count as 'only digits'.

Try It Yourself

How would you modify this to allow a single decimal point (for float numbers)?

Frequency Count

What You'll Learn

Mapping characters to their occurrence counts.

Real-World Context

"Counting how many times each character appears in a string."

Breaking It Down

Initialize an empty map or array of size 256
Iterate through the string
Increment the count for each character

Python 3

from collections import Counter
def char_frequency(s):
    return dict(Counter(s))

Line-by-Line Walkthrough

We use a hash map (or a frequency array) to store the count of each character encountered.

Complexity Analysis

Time: O(N)
Space: O(1) (max 256 for ASCII)
We visit each character once.

Common Mistakes

❌ Using a map in C++ (O(N log K)) instead of unordered_map (O(N))
✅ Use unordered_map for better performance if order doesn't matter.

Try It Yourself

Can you print the characters in descending order of their frequency?

Remove Non-Alphabetic

What You'll Learn

Filtering strings based on character properties.

Real-World Context

"Cleaning a string to keep only letters. 'Hello, 123!' becomes 'Hello'."

Breaking It Down

Iterate through the string
If character is alphabetic, keep it
Otherwise, discard it

Python 3

def remove_non_alpha(s):
    return "".join(c for c in s if c.isalpha())

Line-by-Line Walkthrough

We use the isalpha() function to filter out numbers, spaces, and special characters.

Complexity Analysis

Time: O(N)
Space: O(N)
We create a new string with only alphabetic characters.

Common Mistakes

❌ Forgetting to handle spaces
✅ If you want to keep spaces, add a check for c == ' '.

Try It Yourself

How would you remove only the digits from a string?

String Mastery Continued

You've mastered the core patterns! The remaining questions like "Count Vowels", "Remove Spaces", and "Case Conversion" are simple variations of these loops.

Next: Arrays & Sorting →