Why Strings Are a Data Structure Not Just Text in DSA Typescript - Performance Analysis

Time Complexity: Why Strings Are a Data Structure Not Just Text

O(n)

Understanding Time Complexity

Strings are more than just text; they are a way to organize characters in order. Understanding their time complexity helps us see how operations on strings grow as they get longer.

We want to know how fast or slow common string actions happen as the string size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function countCharacter(str: string, char: string): number {
  let count = 0;
  for (let i = 0; i < str.length; i++) {
    if (str[i] === char) {
      count++;
    }
  }
  return count;
}
    

This code counts how many times a specific character appears in a string.

Identify Repeating Operations

• Primary operation: Looping through each character in the string once.
• How many times: Exactly once for every character in the string (n times).

How Execution Grows With Input

As the string gets longer, the number of checks grows directly with its length.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The work grows in a straight line with the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to count characters grows directly with the string size.

Common Mistake

[X] Wrong: "Checking a character in a string is instant no matter the string size."

[OK] Correct: Each character check takes time, so longer strings mean more checks and more time.

Interview Connect

Understanding string operations and their time costs helps you solve problems efficiently and explain your choices clearly in interviews.

Self-Check

"What if we searched for a substring instead of a single character? How would the time complexity change?"

Practice

1. Why are strings considered a data structure and not just plain text?

easy

A. Because strings are only used for displaying text on the screen.

B. Because strings store characters in a specific order and allow operations like indexing and slicing.

C. Because strings cannot be changed once created.

D. Because strings are only sequences of numbers.

Solution

1. Step 1: Understand what a data structure is

   A data structure organizes data to allow efficient access and modification.

2. Step 2: Analyze string properties

   Strings store characters in order and support operations like indexing, slicing, and searching, which are typical data structure features.

3. Final Answer:

   Because strings store characters in a specific order and allow operations like indexing and slicing. -> Option B

4. Quick Check:

   Strings = Ordered character storage [OK]

Hint: Remember: strings hold ordered characters, not just text [OK]

Common Mistakes:

• Thinking strings are just text without structure
• Confusing immutability with data structure properties
• Assuming strings only display data

2. Which of the following is the correct way to access the third character of a string str in TypeScript?

easy

A. str.charAt(3)

B. str(3)

C. str[2]

D. str.get(2)

Solution

1. Step 1: Recall string indexing in TypeScript

   Strings use zero-based indexing, so the first character is at index 0.

2. Step 2: Identify correct syntax for accessing characters

   Using square brackets with index accesses the character at that position, so str[2] gets the third character.

3. Final Answer:

   str[2] -> Option C

4. Quick Check:

   Index 2 = third character [OK]

Hint: Use zero-based index with square brackets to access characters [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Using 1-based indexing
• Using non-existent methods like get()

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

const s = "hello";
console.log(s[1] + s[4]);

medium

A. "eo"

B. "he"

C. "hl"

D. "lo"

Solution

1. Step 1: Identify characters at given indices

   Index 1 of "hello" is 'e', index 4 is 'o'.

2. Step 2: Concatenate characters

   Concatenating 'e' + 'o' results in "eo".

3. Final Answer:

   "eo" -> Option A

4. Quick Check:

   s[1] + s[4] = "e" + "o" = "eo" [OK]

Hint: Remember string indices start at 0; add characters at given indices [OK]

Common Mistakes:

• Using 1-based indexing
• Mixing up indices and characters
• Assuming output is an array

4. Identify the error in this TypeScript code that tries to change the first character of a string:

let word = "hello";
word[0] = "H";
console.log(word);

medium

A. Strings are immutable; you cannot change characters by index.

B. The syntax for changing characters is incorrect; use parentheses instead of brackets.

C. You must declare the string as a constant to modify it.

D. The console.log statement is missing parentheses.

Solution

1. Step 1: Understand string immutability in TypeScript

   Strings cannot be changed after creation; individual characters cannot be assigned new values.

2. Step 2: Analyze the code behavior

   Trying to assign to word[0] does not change the string; no error but no effect.

3. Final Answer:

   Strings are immutable; you cannot change characters by index. -> Option A

4. Quick Check:

   Strings cannot be changed by index assignment [OK]

Hint: Remember strings are immutable; use new string to change content [OK]

Common Mistakes:

• Trying to assign characters directly by index
• Confusing arrays with strings
• Expecting console.log syntax error

5. Given the string str = "data", which TypeScript code correctly creates a new string with the first character capitalized, demonstrating string as a data structure?

hard

A. const newStr = str.replace(0, str[0].toUpperCase());

B. str[0] = str[0].toUpperCase(); const newStr = str;

C. const newStr = str.toUpperCase()[0] + str[1];

D. const newStr = str[0].toUpperCase() + str.slice(1);

Solution

1. Step 1: Understand string immutability and methods

   You cannot change characters by index, but you can create new strings using methods like toUpperCase() and slice().

2. Step 2: Analyze each option

   const newStr = str[0].toUpperCase() + str.slice(1); correctly creates a new string by capitalizing the first character and appending the rest. str[0] = str[0].toUpperCase(); const newStr = str; tries to assign to index (invalid). const newStr = str.toUpperCase()[0] + str[1]; only capitalizes first char but appends only one character. const newStr = str.replace(0, str[0].toUpperCase()); uses replace incorrectly (replace expects substring, not index).

3. Final Answer:

   const newStr = str[0].toUpperCase() + str.slice(1); -> Option D

4. Quick Check:

   Create new string with methods, not index assignment [OK]

Hint: Use string methods to build new strings; never assign by index [OK]

Common Mistakes:

• Trying to assign to string index
• Using replace with index instead of substring
• Not including full string after first char