String Basics and Memory Representation in DSA Python

Mental Model

A string is a sequence of characters stored one after another in memory, like beads on a string.

Analogy: Imagine a necklace where each bead is a letter. The beads are lined up in order, and you can look at each bead one by one to read the message.

Index:  0   1   2   3   4
String: H -> e -> l -> l -> o -> null
Memory: [H][e][l][l][o]

Dry Run Walkthrough

Input: string: "Hello"

Goal: Understand how each character is stored in memory and accessed by index

Step 1: Store 'H' at index 0

[H] -> null

Why: First character must be stored at the start

Step 2: Store 'e' at index 1

[H] -> [e] -> null

Why: Next character stored right after the first

Step 3: Store 'l' at index 2

[H] -> [e] -> [l] -> null

Why: Continue storing characters in order

Step 4: Store 'l' at index 3

[H] -> [e] -> [l] -> [l] -> null

Why: Store repeated character at next position

Step 5: Store 'o' at index 4

[H] -> [e] -> [l] -> [l] -> [o] -> null

Why: Store last character to complete the string

Result:

[H] -> [e] -> [l] -> [l] -> [o] -> null
String length = 5

Annotated Code

DSA Python

class StringMemory:
    def __init__(self, content):
        self.chars = list(content)  # store characters in list to simulate memory

    def __str__(self):
        # Show characters linked by arrows ending with null
        return ' -> '.join(f'[{c}]' for c in self.chars) + ' -> null'

    def length(self):
        return len(self.chars)

# Driver code
s = StringMemory("Hello")
print(s)
print(f"String length = {s.length()}")

self.chars = list(content) # store characters in list to simulate memory

store each character in order to simulate contiguous memory

return ' -> '.join(f'[{c}]' for c in self.chars) + ' -> null'

visualize string as linked characters ending with null

return len(self.chars)

calculate string length by counting stored characters

Output

[H] -> [e] -> [l] -> [l] -> [o] -> null

String length = 5

Complexity Analysis

Time: O(n) because storing or printing the string requires touching each character once

Space: O(n) because each character is stored separately in memory

vs Alternative: Compared to storing characters separately in scattered memory, contiguous storage allows fast access by index

Edge Cases

empty string ""

stores no characters, length is zero

DSA Python

self.chars = list(content)  # store characters in list to simulate memory

string with one character "A"

stores single character at index 0, length is one

DSA Python

self.chars = list(content)  # store characters in list to simulate memory

When to Use This Pattern

When you see problems about accessing or manipulating characters by position, think of strings as arrays of characters stored in order.

Common Mistakes

Mistake: Thinking strings are stored as single units without individual characters in memory
Fix: Remember strings are sequences of characters stored one after another, allowing access by index

Mistake: Confusing string length with memory size or capacity
Fix: Length counts actual characters stored, not memory reserved

Summary

A string is a sequence of characters stored one after another in memory.

Use this when you need to access or manipulate characters by their position.

The key insight is that each character occupies a spot in order, like beads on a string.

Practice

1. Which of the following statements about Python strings is true?

easy

A. Strings are stored as linked lists in memory.

B. Strings are immutable, meaning they cannot be changed after creation.

C. Strings are mutable and can be changed character by character.

D. Strings always use 4 bytes per character regardless of content.

Solution

1. Step 1: Understand string mutability in Python

   Python strings cannot be changed after they are created. Any modification creates a new string.

2. Step 2: Analyze other options

   Strings are not mutable, not stored as linked lists, and use variable bytes depending on encoding.

3. Final Answer:

   Strings are immutable, meaning they cannot be changed after creation. -> Option B

4. Quick Check:

   Strings are immutable [OK]

Hint: Remember: Python strings cannot be changed once made [OK]

Common Mistakes:

• Thinking strings can be changed in place
• Assuming fixed byte size per character
• Confusing string storage with lists

2. Which of the following is the correct way to create a string in Python?

easy

A. str = 'Hello World'

B. str = Hello World

C. str = "Hello World

D. str = 'Hello World"

Solution

1. Step 1: Check string syntax rules

   Strings must be enclosed in matching single or double quotes.

2. Step 2: Validate each option

   str = 'Hello World' uses matching single quotes correctly. Options B, C, and D have missing or mismatched quotes causing syntax errors.

3. Final Answer:

   str = 'Hello World' -> Option A

4. Quick Check:

   Matching quotes create strings correctly [OK]

Hint: Strings need matching quotes around text [OK]

Common Mistakes:

• Forgetting quotes around string text
• Using mismatched quotes
• Confusing string with variable names

3. What will be the output of the following code?

text = 'abc'
print(id(text))
text += 'd'
print(id(text))

medium

A. Two different numbers printed

B. Same number printed twice

C. SyntaxError

D. RuntimeError

Solution

1. Step 1: Understand string immutability and id()

   Strings are immutable, so adding 'd' creates a new string object with a new id.

2. Step 2: Trace the code output

   First print shows id of 'abc', second print shows id of new string 'abcd', which is different.

3. Final Answer:

   Two different numbers printed -> Option A

4. Quick Check:

   String immutability changes id after modification [OK]

Hint: String id changes after modification due to immutability [OK]

Common Mistakes:

• Assuming string id stays same after += operation
• Confusing id() with value
• Expecting syntax or runtime errors here

4. Find the error in the following code snippet:

my_str = 'hello'
my_str[0] = 'H'
print(my_str)

medium

A. Output: hello

B. SyntaxError: invalid syntax

C. TypeError: 'str' object does not support item assignment

D. Output: Hello

Solution

1. Step 1: Identify string mutability rules

   Strings cannot be changed by assigning to an index because they are immutable.

2. Step 2: Analyze the error raised

   Assigning to my_str[0] causes a TypeError about item assignment not supported.

3. Final Answer:

   TypeError: 'str' object does not support item assignment -> Option C

4. Quick Check:

   Immutable strings cause TypeError on index assignment [OK]

Hint: Strings cannot be changed by index assignment [OK]

Common Mistakes:

• Expecting string to change after index assignment
• Thinking code runs without error
• Confusing TypeError with SyntaxError

5. Given the code below, what will be the output?

str1 = 'abc'
str2 = 'abc'
print(str1 is str2)
str3 = ''.join(['a', 'b', 'c'])
print(str1 is str3)

hard

A. False\nTrue

B. False\nFalse

C. True\nTrue

D. True\nFalse

Solution

1. Step 1: Understand string interning for literals

   Python reuses the same object for identical string literals, so str1 and str2 point to the same object.

2. Step 2: Understand string creation with join()

   str3 is created at runtime and is a new object, so str1 is not str3.

3. Final Answer:

   True\nFalse -> Option D

4. Quick Check:

   Literal strings share object, runtime strings do not [OK]

Hint: Literal strings share memory; constructed strings do not [OK]

Common Mistakes:

• Assuming all identical strings share same object
• Confusing 'is' with '=='
• Ignoring how strings are created