Strings and Character Arrays

Learn how strings work as character arrays: immutability, Unicode, efficient string building, two-pointer tricks and frequency counting in Python.

• Beginner
• 16 min read
• 4 objectives

Before this lessonLesson 3: Arrays

Almost every program handles text: usernames, URLs, log lines, JSON, search queries. Under the hood a string is an array of characters, so everything you learned about arrays (fast indexing, slow inserts in the middle) applies. But strings add a few twists of their own: in Python and many other languages they are immutable, and characters are Unicode code points rather than simple bytes.

In this lesson you will see how those twists affect performance, and you will learn the handful of techniques that solve most string problems in interviews and real code.

A string is a sequence of characters

Like an array, a string stores its characters in order, and each has an index starting at 0. Reading s[i] is O(1). Slicing s[a:b] creates a brand new string, so it costs O(b - a) time and memory.

s = "stackcone"
print(s[0], s[-1])
print(s[0:5])
print(len(s))
for i, ch in enumerate(s[:3]):
    print(i, ch)

s e
stack
9
0 s
1 t
2 a

Immutability: strings cannot be changed in place

In Python, Java, JavaScript and C#, strings are immutable. Once created, their characters never change. Any "modification" builds a new string. This makes strings safe to share and to use as dictionary keys, because nobody can change a key after it has been hashed.

name = "ada"
try:
    name[0] = "A"
except TypeError as e:
    print("Error:", e)

upper = name.capitalize()   # builds a new string
print(name, upper)

Error: 'str' object does not support item assignment
ada Ada

When you need to edit characters one by one, convert the string into a real character array (a Python list), edit the list, and join it back at the end.

chars = list("hello")
chars[0] = "j"
chars.append("!")
print(chars)
print("".join(chars))

['j', 'e', 'l', 'l', 'o', '!']
jello!

Building strings efficiently

Because each + creates a new string, concatenating in a loop can copy the growing result again and again. Adding n pieces this way can cost O(n squared) character copies. The fix is to collect pieces in a list and call join once, which is O(total length).

words = ["orders", "users", "payments", "invoices"]

# Collect parts, join once: O(total length)
parts = []
for w in words:
    parts.append(w.upper())
print(", ".join(parts))

# Same idea with a generator expression
print("-".join(w[0] for w in words))

ORDERS, USERS, PAYMENTS, INVOICES
o-u-p-i

Characters are Unicode, not bytes

A Python str holds Unicode code points. len counts code points, not bytes. When text is saved to disk or sent over a network it is encoded, usually as UTF-8, where one character can take 1 to 4 bytes. ord and chr convert between a character and its number.

word = "café"
print(len(word), len(word.encode("utf-8")))
print(ord("a"), chr(98))
print([ord(c) - ord("a") for c in "abc"])

4 5
97 b
[0, 1, 2]

The trick ord(c) - ord("a") maps lowercase letters to 0 to 25, which lets you use a fixed array of 26 counters instead of a dictionary.

Technique 1: two pointers

Many string questions compare characters from both ends. Put one pointer at the start and one at the end, and move them toward each other. This checks a palindrome in O(n) time and O(1) extra space, without building a reversed copy.

def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if not s[i].isalnum():
            i += 1
        elif not s[j].isalnum():
            j -= 1
        elif s[i].lower() != s[j].lower():
            return False
        else:
            i += 1
            j -= 1
    return True

print(is_palindrome("A man, a plan, a canal: Panama"))
print(is_palindrome("stackcone"))

True
False

Technique 2: frequency counting

Counting how often each character appears solves anagram checks, "first unique character" and many more. A collections.Counter is a hash map of counts. Building it is O(n).

from collections import Counter

def is_anagram(a, b):
    return Counter(a) == Counter(b)

print(is_anagram("listen", "silent"))
print(is_anagram("orders", "sorted"))

def first_unique(s):
    counts = Counter(s)
    for i, ch in enumerate(s):
        if counts[ch] == 1:
            return i
    return -1

print(first_unique("stackcone"))

True
False
0

Technique 3: sliding window

A sliding window keeps a range [left, right] that grows on the right and shrinks on the left when a rule is broken. The classic example is the longest substring without repeating characters. Each index enters and leaves the window at most once, so it runs in O(n).

def longest_unique(s):
    last_seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))
print(longest_unique("stackcone"))

3
5

Cost of common operations

Operation                      Time          Notes
s[i]                           O(1)          index into the character array
len(s)                         O(1)          length is stored
s[a:b]                         O(b - a)      copies into a new string
s + t                          O(len s + len t)  builds a new string
x in s / s.find(x)             O(n * m) worst  usually fast in practice
"".join(parts)                 O(total)      the right way to build text
s.split(), s.replace()         O(n)          scan the whole string
s == t                         O(n)          compares character by character

Comparing two strings is not O(1): Python checks lengths first and then characters until they differ. That is one reason hashing long strings (as dictionary keys do) costs O(length), although Python caches a string's hash after the first time.

Recap

• A string is an ordered array of characters with O(1) indexing and O(k) slicing.
• Strings are immutable in Python, Java and JavaScript; convert to a list to edit characters.
• Build text with "".join(parts), not repeated +=, to stay linear.
• len counts code points; UTF-8 bytes can be more.
• Two pointers, frequency counts and sliding windows solve most string problems in O(n).

# Write your solution here