StringsLesson 2

String Operations

Reverse, concatenate, compare, find substrings, check palindromes — core string operations with complexity analysis.

What Is It?

Strings come with a set of useful operations: find the length, join two strings together, flip one backwards, compare two strings, pull out a piece of a string, search for a word inside another, and check if something is a palindrome.

Under the hood, every one of these operations is just reading, copying, and comparing characters one by one. There's no magic. Concatenation copies characters from both strings into a new one. Reversal swaps characters from the two ends. Search checks characters at each position for a match.

Knowing how each operation works tells you how fast — or slow — it really is. A developer who thinks joining strings is "free" will accidentally write code that gets slower and slower as data grows.

Analogy

The Typesetter's Workshop

Imagine a typesetter working with physical letter blocks arranged on a tray.

LENGTH: Count the blocks on the tray. If there's a counter on the side, read it instantly. If not, count one by one.
CONCATENATION: Take two trays and combine them onto a new, longer tray. You must physically move every block from both.
REVERSAL: Pick up blocks from both ends at the same time, swapping their positions, working toward the middle.
COMPARISON: Hold two trays side by side. Compare the first block of each. If they match, compare the second blocks. Stop when you find a difference.
SEARCH: Slide a small pattern tray along the main tray, checking at each position whether the blocks match.

Every operation means physically handling blocks. The cost depends on how many you touch.

How It Works

LENGTH — O(1) or O(n)

With a length-prefixed string, just read the stored number:

pseudocode

function length(str):
    return str.storedLength    // O(1) — instant

With a null-terminated string, scan until you hit the end marker:

pseudocode

function length(str):
    count = 0
    while str[count] != '\0':
        count = count + 1
    return count               // O(n) — slower for longer strings

This difference matters. If you call length() inside a loop on a null-terminated string, it scans the whole string on every iteration — turning O(n) code into O(n²):

pseudocode

// SLOW — length() scans the string on every loop iteration:
for i = 0 to length(str) - 1:
    process(str[i])
// FAST — compute length once before the loop:
len = length(str)
for i = 0 to len - 1:
    process(str[i])

CONCATENATION — O(n + m)

Joining two strings means creating a brand new string and copying all characters from both into it.

pseudocode

function concatenate(str1, str2):
    len1 = length(str1)
    len2 = length(str2)
    result = allocate(len1 + len2)
    for i = 0 to len1 - 1:
        result[i] = str1[i]
    for i = 0 to len2 - 1:
        result[len1 + i] = str2[i]
    return result

Trace — joining "Hello" + " World":

pseudocode

str1: ['H','e','l','l','o']           length = 5
str2: [' ','W','o','r','l','d']       length = 6
result = allocate(11)
Copy str1: result = ['H','e','l','l','o', _, _, _, _, _, _]
Copy str2: result = ['H','e','l','l','o',' ','W','o','r','l','d']
Total characters copied: 5 + 6 = 11 → O(n + m)

REVERSE — O(n)

Reverse a string by swapping characters from the two ends, moving toward the middle. Use two variables — one starting at the left, one at the right.

pseudocode

function reverse(chars):
    left = 0
    right = length(chars) - 1
    while left < right:
        temp = chars[left]
        chars[left] = chars[right]
        chars[right] = temp
        left = left + 1
        right = right - 1

Trace with "ABCDE":

pseudocode

Start:    ['A','B','C','D','E']    left=0, right=4
Swap A↔E: ['E','B','C','D','A']   left=1, right=3
Swap B↔D: ['E','D','C','B','A']   left=2, right=2
left == right → stop (middle element stays put)
Result: ['E','D','C','B','A']

Note: if the string is immutable (can't be changed), you must create a new character array, fill it in reverse, and build a new string from that.

COMPARE — O(n)

Lexicographic comparison means comparing strings character by character using their numeric codes — the same way a dictionary orders words.

pseudocode

function compare(str1, str2):
    i = 0
    while i < length(str1) and i < length(str2):
        if str1[i] < str2[i]:
            return -1          // str1 comes first
        else if str1[i] > str2[i]:
            return 1           // str2 comes first
        i = i + 1
    if length(str1) < length(str2):
        return -1
    else if length(str1) > length(str2):
        return 1
    else:
        return 0               // exactly equal

Examples:

compare("apple", "banana"):
  'a'(97) vs 'b'(98) → 'a' < 'b' → return -1 ("apple" comes first)
compare("cat", "car"):
  'c' vs 'c' → equal, keep going
  'a' vs 'a' → equal, keep going
  't'(116) vs 'r'(114) → 't' > 'r' → return 1 ("cat" comes after "car")
compare("app", "apple"):
  all three letters match
  str1 runs out first → return -1 ("app" comes before "apple")

SUBSTRING — O(k) where k is the length of the piece you want

Pull out a chunk of the string from one index to another.

pseudocode

function substring(str, start, end):
    subLen = end - start
    result = allocate(subLen)
    for i = 0 to subLen - 1:
        result[i] = str[start + i]
    return result

Trace — substring("HELLO WORLD", 6, 11):

pseudocode

str:    ['H','E','L','L','O',' ','W','O','R','L','D']
index:    0   1   2   3   4   5   6   7   8   9  10
start=6, end=11, subLen=5
Copy positions 6 through 10: ['W','O','R','L','D']
Result: "WORLD"

SEARCH (Naive) — O(n × m)

Find the first place a short pattern appears inside a longer text. The simple approach: try every starting position.

pseudocode

function naiveSearch(text, pattern):
    n = length(text)
    m = length(pattern)
    for i = 0 to n - m:
        match = true
        for j = 0 to m - 1:
            if text[i + j] != pattern[j]:
                match = false
                break
        if match:
            return i       // found it! starts at index i
    return -1              // not found

Trace — searching for "LO" in "HELLO":

i=0: text[0..1] = "HE" vs "LO" → H≠L → no match
i=1: text[1..2] = "EL" vs "LO" → E≠L → no match
i=2: text[2..3] = "LL" vs "LO" → L=L, L≠O → no match
i=3: text[3..4] = "LO" vs "LO" → L=L, O=O → MATCH at index 3

Worst case is O(n × m) — takes longer the longer both strings are.

PALINDROME CHECK — O(n)

A palindrome is a word that reads the same forwards and backwards — like "racecar" or "level". Check it with two pointers: one at the start, one at the end, both moving toward the middle.

pseudocode

function isPalindrome(str):
    left = 0
    right = length(str) - 1
    while left < right:
        if str[left] != str[right]:
            return false
        left = left + 1
        right = right - 1
    return true

Trace with "RACECAR":

pseudocode

left=0, right=6: 'R' == 'R' ✓
left=1, right=5: 'A' == 'A' ✓
left=2, right=4: 'C' == 'C' ✓
left=3, right=3: left == right → stop
Return true.

Trace with "HELLO":

left=0, right=4: 'H' != 'O' → return false immediately.

Examples

Example 1: Why concatenation in a loop is expensive

result = ""
for i = 0 to 4:
    result = concatenate(result, "ab")
// Iteration 0: concat("" + "ab")         → copy 2 chars  → "ab"
// Iteration 1: concat("ab" + "ab")       → copy 4 chars  → "abab"
// Iteration 2: concat("abab" + "ab")     → copy 6 chars  → "ababab"
// Iteration 3: concat("ababab" + "ab")   → copy 8 chars  → "abababab"
// Iteration 4: concat("abababab" + "ab") → copy 10 chars → "ababababab"
//
// Total characters copied: 2+4+6+8+10 = 30
// For n iterations, this grows as n² — gets very slow very fast.

Example 2: Full search walkthrough

Searching for "CD" in "ABCDEF":

i=0: A=C? No  → skip
i=1: B=C? No  → skip
i=2: C=C? Yes! D=D? Yes! → Match found at index 2

Common Mistakes

Concatenating strings inside a loop. Every concatenation copies everything accumulated so far. Do this n times and you copy 1 + 2 + 3 + ... + n characters — that's O(n²). Use a string builder instead (next lesson).

Comparing strings with == when it checks the wrong thing. In many languages, str1 == str2 checks whether the two variables point to the same object in memory, not whether the characters match. Use the compare function to check actual contents.

Off-by-one in substring. Does substring(str, 2, 5) include index 5 or stop at 4? This varies. Always double-check whether the end index is inclusive or exclusive.

Forgetting that comparison is case-sensitive. 'A' (65) and 'a' (97) have different codes. "Apple" and "apple" are not equal unless you normalize the case first.

Best Practices

Store the string length in a variable before a loop — never recalculate it inside the loop condition
Avoid concatenation inside loops — use a string builder (covered in the next lesson)
When comparing strings, decide upfront whether case matters and handle it explicitly
When using substring, write a comment clarifying whether your end index is inclusive or exclusive

How Strings Work String Immutability and Builders