String Building, Palindromes and Counting

26 min · Intermediate

Strings are sequences of characters that you cannot change. Most string problems come down to three tools: build the answer in a list and join, walk from both ends, or count with a table.

Build strings with join

str.join builds one string from many strings, with a separator placed between them. It is the usual way to assemble text, because a string cannot be changed in place.

A report line is made of many small pieces. Strings cannot be changed, so += in a loop may copy the growing text each time. Collect the pieces in a list and join them once.

Python

parts = []for n in range(1, 6):    parts.append(str(n * n))print(", ".join(parts))

Example 1 · Mask an order id

Python

ticket = "TK20481357"masked = "*" * (len(ticket) - 4) + ticket[-4:]print(masked)

Output

******1357

What this code does

"*" * 6 repeats the star six times.
ticket[-4:] keeps the last four characters.
Joining the two parts builds the final text once.

Example 2 · Join with a format for each piece

Python

marks = {"Asha": 91, "Ravi": 78, "Meena": 85}print(", ".join(f"{name}:{mark}" for name, mark in marks.items()))

Output

Asha:91, Ravi:78, Meena:85

What this code does

The generator makes one small string per student.
join puts ", " between them, and no separator is left at the end.
Doing the same with += needs special care for the last comma.

join is called on the separator and takes a list of strings. The pieces must already be strings.

Palindromes with two pointers

Palindrome means a text that reads the same forwards and backwards, such as level. Checks often ignore case, spaces and punctuation.

A palindrome reads the same forwards and backwards. Compare the first and last characters, then move inward. Skip anything that is not a letter or a digit, and ignore capital letters.

Python

1text = "A man, a plan, a canal: Panama"2left, right = 0, len(text) - 13ok = True4while left < right:5    if not text[left].isalnum():6        left += 17    elif not text[right].isalnum():8        right -= 19    elif text[left].lower() != text[right].lower():10        ok = False11        break12    else:13        left += 114        right -= 115print(ok)

Example 3 · A palindrome the short way

Python

1def is_palindrome(text):2    letters = [c.lower() for c in text if c.isalnum()]3    return letters == letters[::-1]4
5
6print(is_palindrome("Was it a car or a cat I saw?"))7print(is_palindrome("Order 66"))

Output

True
False

What this code does

The comprehension keeps only letters and digits, in lower case.
A list equals its reverse exactly when the text is a palindrome.
O(n) time and O(n) space. The pointer version in the section uses O(1) space.

Example 4 · Longest palindrome by expanding

Python

1def longest_palindrome(s):2    best = ""3    for centre in range(len(s)):4        for lo, hi in ((centre, centre), (centre, centre + 1)):5            while lo >= 0 and hi < len(s) and s[lo] == s[hi]:6                lo -= 17                hi += 18            if hi - lo - 1 > len(best):9                best = s[lo + 1:hi]10    return best11
12
13print(longest_palindrome("babad"))14print(longest_palindrome("forgeeksskeegfor"))

Output

bab
geeksskeeg

What this code does

Every palindrome grows outward from a centre. The centre is a letter (odd length) or a gap between two letters (even length).
Each centre expands while both ends match, and the longest result is kept.
O(n squared) time and O(1) extra space.

No cleaned copy is made, so the extra space is O(1). Time is O(n).

Count with a dictionary or Counter

Frequency count means a table that maps each distinct item to how many times it appears. It is built in one pass, in O(n) time.

Frequency counting answers: how many times does each item appear? Walk once and add one to a slot in a dictionary. Counter from the standard library does the same in one line.

Python

1from collections import Counter2
3word = "mississippi"4counts = {}5for ch in word:6    counts[ch] = counts.get(ch, 0) + 17print(counts)8print(Counter(word))

Example 5 · Most common characters

Python

from collections import Counter
print(Counter("mississippi").most_common(2))

Output

[('i', 4), ('s', 4)]

What this code does

most_common(2) returns the two biggest counts as (item, count) pairs.
Equal counts keep the order in which the items first appeared.
Counting is O(n); picking the top few is cheap.

Both take O(n) time. A missing key in a Counter gives 0, while a plain dictionary needs .get.

Anagrams and the first unique character

Two words are anagrams if they use the same letters the same number of times, so their counts are equal. The same count table also finds the first character that appears only once.

Python

1from collections import Counter2
3print(Counter("listen") == Counter("silent"))4word = "swiss"5counts = Counter(word)6print(next((c for c in word if counts[c] == 1), None))

Example 6 · Group words that are anagrams

Python

words = ["listen", "silent", "enlist", "google", "gogole", "cat"]groups = {}for word in words:    groups.setdefault("".join(sorted(word)), []).append(word)print(list(groups.values()))

Output

[['listen', 'silent', 'enlist'], ['google', 'gogole'], ['cat']]

What this code does

Words that are anagrams have the same letters when sorted, so the sorted text is a key.
setdefault creates an empty list the first time a key is seen.
Time is O(n * k log k) for n words of length k.

The second pass goes through the word, not the table, so the original order decides which character is first.

Next step

Check your understanding

11 quick questions

Build strings with join

str.join builds one string from many strings, with a separator placed between them. It is the usual way to assemble text, because a string cannot be changed in place.

A report line is made of many small pieces. Strings cannot be changed, so += in a loop may copy the growing text each time. Collect the pieces in a list and join them once.

Palindromes with two pointers

Palindrome means a text that reads the same forwards and backwards, such as level. Checks often ignore case, spaces and punctuation.

A palindrome reads the same forwards and backwards. Compare the first and last characters, then move inward. Skip anything that is not a letter or a digit, and ignore capital letters.

1text = "A man, a plan, a canal: Panama"2left, right = 0, len(text) - 13ok = True4while left < right:5 if not text[left].isalnum():6 left += 17 elif not text[right].isalnum():8 right -= 19 elif text[left].lower() != text[right].lower():10 ok = False11 break12 else:13 left += 114 right -= 115print(ok)

1def is_palindrome(text):2 letters = [c.lower() for c in text if c.isalnum()]3 return letters == letters[::-1]4 5 6print(is_palindrome("Was it a car or a cat I saw?"))7print(is_palindrome("Order 66"))

1def longest_palindrome(s):2 best = ""3 for centre in range(len(s)):4 for lo, hi in ((centre, centre), (centre, centre + 1)):5 while lo >= 0 and hi < len(s) and s[lo] == s[hi]:6 lo -= 17 hi += 18 if hi - lo - 1 > len(best):9 best = s[lo + 1:hi]10 return best11 12 13print(longest_palindrome("babad"))14print(longest_palindrome("forgeeksskeegfor"))

Count with a dictionary or Counter

Frequency count means a table that maps each distinct item to how many times it appears. It is built in one pass, in O(n) time.

Frequency counting answers: how many times does each item appear? Walk once and add one to a slot in a dictionary. Counter from the standard library does the same in one line.