Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 225 ยท Strings

Strings in DSA

Understand how strings behave in algorithms: immutability, the cost of concatenation and slicing, join, Unicode versus ASCII, and counting characters.

A string is a sequence of characters, so almost everything you learned about arrays carries over: you index it, slice it, loop over it and compare positions. But strings have a few properties that change how you analyze and write algorithms. The biggest one is that Python strings are immutable: you can never change a character in place. That single fact explains why some innocent-looking code is accidentally quadratic.

In this lesson you will learn what immutability costs, which string operations are O(1) and which are O(n), how to build strings efficiently, how characters map to numbers with ord and chr, and how to count character frequencies with a dict, a Counter or a fixed-size array. These are the building blocks for classic string problems, pattern matching and hashing.

Strings are immutable sequences

You can read a character by index, but you cannot assign to one:

Python Immutability (the error is on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every "modification" creates a brand-new string. word.upper(), word.replace(...), word + "!" all return new objects and leave the original alone. Immutability makes strings safe to share and, importantly, lets them be dictionary keys and set members, which hashing algorithms rely on.

TEXT
word    -> "hello"            (never changes)
changed -> "Jello"            (a different object, O(n) to build)

What costs what

Let n be the length of the string.

Operation Time Notes
len(s), s[i] O(1) length is stored; indexing is direct
s[i:j] O(j - i) slicing copies the characters
s + t O(len(s) + len(t)) a new string is built
s == t O(n) stops at the first difference, worst case compares all
t in s, s.find(t) O(n * m) worst case substring search, see pattern matching
s.upper(), s.replace(), s.split() O(n) one pass, new string(s)
hash(s) O(n) the first time CPython caches the result in the string

The cost that surprises beginners is slicing. In an algorithm that slices inside a loop (for example, s[i:] on every recursive call), the copying alone is O(nยฒ). Prefer passing indexes instead of slices.

Python Slicing copies, indexes do not

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Slicing 600 times copies about 180,000 characters in total; the index version just takes 600 steps. Doubling the length would multiply the slicing total by about four. That is the signature of O(nยฒ).

Building strings: the concatenation trap

Because s += ch creates a new string, building a long string with a loop looks like O(nยฒ): each step copies everything built so far. (CPython sometimes optimises += in place when nothing else references the string, but you must never rely on that, and other Python implementations do not do it.) The portable, always-linear pattern is: collect pieces in a list, then "".join(pieces) once.

Python Count the characters copied by naive concatenation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For n = 1000 the naive model copies 500,500 characters, versus 1,000 for the join approach. Reversing, filtering and transforming are usually written as a list or generator expression passed to join, for example "".join(c for c in s if c.isalpha()).

If you need to change characters one at a time, convert to a list with chars = list(s), edit chars[i], and join back with "".join(chars). That is the Python way to get a mutable string, and it costs O(n) once, not per edit.

Characters are numbers: ord and chr

Every character has an integer code point. ord("a") gives 97, and chr(97) gives back "a". For the English alphabet the lowercase letters are consecutive, so ord(ch) - ord("a") maps a..z to 0..25. This is the basis of many tricks: Caesar ciphers, counting arrays, comparing letters.

Python ord, chr and a Caesar shift

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Comparing strings with < is lexicographic: character by character by code point. That is why uppercase letters sort before lowercase ones ("Z" < "a").

ASCII and Unicode

ASCII defines 128 characters: English letters, digits, punctuation and control codes. Unicode extends this to over a million possible code points covering every writing system plus emoji. A Python 3 str is a sequence of Unicode code points, so len("hรฉllo") is 5 even though the text needs more than 5 bytes when saved as UTF-8.

Python Characters versus bytes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For interview problems, check what the character set is: "lowercase English letters" lets you use a 26-slot array; "any Unicode character" calls for a dictionary. Note that a single visible symbol can be several code points (for example some emoji with skin tones), a detail you can ignore unless a problem raises it.

Counting characters

Frequency counting is the most reused string technique: anagrams, first unique character, ransom notes, sliding windows all need it. There are three ways, and each has a place.

Python Three ways to count characters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three run in O(n) time. Space is O(k), where k is the number of distinct characters: at most 26 for lowercase English, so the array and the dict are O(1) space in that setting, and O(n) in the worst case for arbitrary Unicode.

Method Pros Cons
dict any characters slightly more code
Counter shortest, has most_common, supports + and - tiny overhead
26-slot array fastest, easy to compare only for a known small alphabet

Comparing two arrays of 26 numbers is O(26) = O(1), which is a favorite trick in sliding window problems: you can check "is this window an anagram of the pattern" in constant time per step.

Useful string methods for algorithms

Python Handy methods

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two details worth remembering: find returns -1 when there is no match (while index raises ValueError), and count("aa") on "aaaa" is 2, not 3, because matches do not overlap.

Common mistakes

  • Trying to assign s[i] = x. Strings are immutable; use a list of characters.
  • Concatenating in a loop on huge data. Collect pieces, then join.
  • Slicing inside loops or recursion. Pass indexes lo and hi instead.
  • Forgetting that == is O(n). Comparing two long strings repeatedly adds a hidden factor.
  • Assuming 26 letters. Check whether input has uppercase, digits or Unicode.
  • Using str as a variable name. It hides the built-in type.
  • Off-by-one in ord arithmetic. ord(ch) - ord("a") for lowercase; do not mix cases.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does word[0] = 'J' raise a TypeError?

    Python strings never change after creation. To get a different string you build a new one, for example by slicing and concatenating.
  2. 2. What is the best way to build a long string from many small pieces?

    join allocates the final string once, so the whole build is O(n) instead of repeatedly copying the growing string.
  3. 3. What does the expression ord('d') - ord('a') evaluate to?

    The letters are consecutive code points, so d is three positions after a.
  4. 4. What is the time complexity of s[i:] for a string of length n?

    A slice copies the characters it contains, so the cost is proportional to the length of the result.
  5. 5. For counting letters in a string of lowercase English letters only, what is the extra space of a 26-slot array?

    The array size depends on the alphabet, not on the input length, so it is a constant 26 slots.

Summary

  • Python strings are immutable sequences of Unicode code points; every change builds a new string.
  • Indexing and len are O(1); slicing, concatenation, comparison and most methods are O(n).
  • Avoid slicing in loops and recursion (pass indexes) and avoid += in long loops (use a list and join).
  • ord and chr convert between characters and integers; ord(ch) - ord("a") maps letters to 0..25.
  • Count characters with a dict, Counter, or a 26-slot array: O(n) time, O(k) space.
  • Always check the alphabet in the problem statement before choosing a data structure.

Next: Classic String Problems, where you will put these tools to work on palindromes, anagrams and more.