How Strings Work Differently Across Languages in DSA Go - Complexity Walkthrough

Time Complexity: How Strings Work Differently Across Languages

O(n²)

Understanding Time Complexity

Strings are handled differently in programming languages, affecting how fast operations run.

We want to see how these differences change the time it takes to work with strings.

Scenario Under Consideration

Analyze the time complexity of the following Go code that concatenates strings.

package main
import "fmt"
func main() {
    s := ""
    for i := 0; i < 5; i++ {
        s += "a"
    }
    fmt.Println(s)
}
    

This code adds the letter 'a' to a string five times using the += operator.

Identify Repeating Operations

Look at what repeats inside the loop.

• Primary operation: Adding one character to the string each time.
• How many times: 5 times (once per loop iteration).

How Execution Grows With Input

Each time we add a character, the whole string is copied to a new space because strings are immutable in Go.

Input Size (n)	Approx. Operations
10	1 + 2 + ... + 10 = 55 copies
100	1 + 2 + ... + 100 = 5050 copies
1000	1 + 2 + ... + 1000 = 500500 copies

Pattern observation: The work grows much faster than the number of characters added because each addition copies the whole string again.

Final Time Complexity

Time Complexity: O(n²)

This means if you add n characters one by one, the total work grows roughly like n times n, because each addition copies the whole string.

Common Mistake

[X] Wrong: "Adding characters one by one to a string is always fast and takes O(n) time."

[OK] Correct: In Go, strings are immutable, so each addition creates a new string by copying all characters, making it slower than expected.

Interview Connect

Understanding how strings behave in different languages helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we used a string builder or buffer instead of += for concatenation? How would the time complexity change?"

Practice

1. In Go, what is the type of a string internally?
var s = "hello"

easy

A. A sequence of bytes representing UTF-8 encoded characters

B. An array of Unicode code points (runes)

C. A linked list of characters

D. A pointer to a null-terminated character array

Solution

1. Step 1: Understand Go string representation

   Go strings are immutable sequences of bytes, typically UTF-8 encoded.

2. Step 2: Compare with other languages

   Unlike some languages that use arrays of Unicode code points, Go uses bytes internally.

3. Final Answer:

   A sequence of bytes representing UTF-8 encoded characters -> Option A

4. Quick Check:

   Go strings = UTF-8 bytes [OK]

Hint: Remember Go strings are byte sequences, not rune arrays [OK]

Common Mistakes:

• Thinking Go strings store runes directly
• Assuming null-terminated strings like C
• Confusing with linked list or array types

2. Which of the following is the correct way to get the length of a string in Go?
s := "hello"

easy

A. length(s)

B. s.length()

C. len(s)

D. s.len

Solution

1. Step 1: Recall Go built-in function for length

   Go uses the built-in function len() to get the length of strings and slices.

2. Step 2: Check other options

   Methods like s.length() or s.len do not exist in Go; length(s) is not valid syntax.

3. Final Answer:

   len(s) -> Option C

4. Quick Check:

   Use len() for string length in Go [OK]

Hint: Use len() function to get string length in Go [OK]

Common Mistakes:

• Using method calls like s.length() from other languages
• Trying to access length as a property
• Using undefined functions like length()

3. What will be the output of this Go code?

package main
import "fmt"
func main() {
  s := "Go😊"
  fmt.Println(len(s))
}

medium

A. 3

B. 6

C. 4

D. 5

Solution

1. Step 1: Analyze string content and encoding

   The string "Go😊" has 'G' and 'o' as 1 byte each, and the emoji '😊' is a 4-byte UTF-8 character.

2. Step 2: Calculate total byte length

   Total bytes = 1 (G) + 1 (o) + 4 (😊) = 6 bytes.

3. Step 3: Check len() output

   len(s) returns the number of bytes, so output is 6.

4. Final Answer:

   6 -> Option B

5. Quick Check:

   len() counts bytes, not characters [OK]

Hint: len() returns bytes count, not character count [OK]

Common Mistakes:

• Assuming len() returns number of characters
• Ignoring multi-byte UTF-8 characters
• Confusing bytes with runes

4. Identify the error in this Go code that tries to print each character of a string:

package main
import "fmt"
func main() {
  s := "Go"
  for i := 0; i < len(s); i++ {
    fmt.Println(s[i])
  }
}

medium

A. It prints byte values, not characters

B. Syntax error in for loop

C. s[i] is invalid syntax

D. Missing import for fmt

Solution

1. Step 1: Understand s[i] in Go strings

   Accessing s[i] returns the byte at index i, not a character or string.

2. Step 2: Check output of fmt.Println(s[i])

   It prints the numeric byte value (ASCII code), not the character itself.

3. Final Answer:

   It prints byte values, not characters -> Option A

4. Quick Check:

   s[i] = byte, prints number [OK]

Hint: s[i] gives byte, convert to rune or string to print char [OK]

Common Mistakes:

• Expecting s[i] to print characters directly
• Ignoring byte vs rune difference
• Assuming syntax error where none exists

5. How can you correctly iterate over each Unicode character in a Go string to print them?
Choose the correct code snippet.

hard

A. for i := 0; i < len(s); i++ { fmt.Println(string(s[i])) }

B. for i := range s { fmt.Println(s[i]) }

C. for i, c := range s { fmt.Println(s[i]) }

D. for _, r := range s { fmt.Println(string(r)) }

Solution

1. Step 1: Understand iteration over strings in Go

   Using 'for _, r := range s' iterates over runes (Unicode code points), not bytes.

2. Step 2: Check printing each character

   Converting rune 'r' to string prints the actual character correctly.

3. Step 3: Analyze other options

   for i := 0; i < len(s); i++ { fmt.Println(string(s[i])) } prints bytes as strings, which may break multi-byte chars; C and D print bytes, not runes.

4. Final Answer:

   for _, r := range s { fmt.Println(string(r)) } -> Option D

5. Quick Check:

   Use range to get runes for correct Unicode iteration [OK]

Hint: Use 'for _, r := range s' to iterate Unicode chars [OK]

Common Mistakes:

• Iterating by byte index instead of runes
• Printing bytes as characters causing errors
• Confusing index and rune variables