Strings as Data Structures

Analogy categoryAnalogies

Introduction

A string is a sequence of characters, and it can be thought of as a specialized array where each element is a single character. In Python, strings are immutable, meaning once a string object is created, its contents can never be changed in place; any operation that appears to 'modify' a string actually creates a new string object.

🏏

Cricket analogy: A scorecard string like 'SACHIN' is a row of character-cells just like a batting-order array, and once the scorebook entry is inked for an innings it is never edited in place — a correction becomes a brand-new entry.

Explanation

Because strings share the underlying array-like layout, indexing a character with s[i] is O(1), and slicing s[a:b] is O(k) where k is the length of the slice, since a new string of that length must be copied. Immutability has major performance implications: concatenating strings in a loop using += is a classic anti-pattern because each concatenation creates a brand-new string and copies all previous characters, turning what looks like an O(n) loop into O(n^2) total work. The idiomatic fix is to collect pieces in a list and join them once with ''.join(pieces), which is O(n) overall. Common string operations include searching for a substring (naive search is O(n*m) for text length n and pattern length m), reversing (O(n)), and checking for palindromes (O(n)).

🏏

Cricket analogy: Checking who's on strike, s[i], is instant like glancing at the scoreboard, but pulling a highlight reel of overs 10 to 15, s[a:b], takes time proportional to those overs since the clip must be copied fresh; repeatedly rebuilding the whole match commentary line by line with += is far slower than collecting each ball's commentary in a list and joining it once at the end.

Example

python

# Inefficient: O(n^2) due to repeated string copying
def build_bad(n):
    s = ""
    for i in range(n):
        s += str(i)   # creates a new string object every time
    return s

# Efficient: O(n) using a list and a single join
def build_good(n):
    pieces = []
    for i in range(n):
        pieces.append(str(i))
    return "".join(pieces)

# O(1) indexing, O(k) slicing
text = "hello world"
print(text[0])       # 'h'
print(text[6:])      # 'world'

# O(n) palindrome check using two pointers
def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))    # False

Complexity

Character access s[i] is O(1). Slicing s[a:b] is O(k) for slice length k because a new string is allocated and copied. Naive substring search is O(n*m); Python's built-in in operator and str.find use optimized algorithms that are typically faster in practice. Reversing or scanning a string is O(n). Repeated concatenation with += inside a loop is O(n^2) total; using list accumulation plus ''.join is O(n) total.

🏏

Cricket analogy: Fetching the batter at index i is instant, slicing an over's ball-by-ball text costs proportional to its length, and scanning the whole commentary for 'SIX' with naive search is O(n*m) while a built-in fast search beats manual scanning; reversing the innings order is O(n).

Key Takeaways

Python strings are immutable; every 'modification' actually creates a new string object.
Character indexing is O(1) and slicing is O(k), but repeated += concatenation in a loop is O(n^2) overall.
Use ''.join(list_of_pieces) to build strings efficiently in O(n) total time.
Two-pointer techniques (like palindrome checks) work naturally on strings because they support O(1) indexed access.

Practice what you learned

1. Why are Python strings considered immutable?

2. What is the total time complexity of building a string of length n using `s += str(i)` in a loop?

3. What is the recommended efficient way to build a large string from many pieces in Python?

4. What is the time complexity of accessing a single character s[i] in a Python string?

Was this page helpful?

Multidimensional Arrays

Common Array and String Problems

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#StringsAsDataStructures#Strings#Data#Structures#Explanation#StudyNotes#SkillVeris