Common string methods in Java - Time & Space Complexity

schedule

Time Complexity: Common string methods

O(n)

menu_book

Understanding Time Complexity

We want to understand how long common string methods take to run as the string gets bigger.

How does the time needed change when the string length grows?

code_blocks

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

String s = "hello world";
int length = s.length();
char c = s.charAt(3);
String sub = s.substring(0, 5);
boolean contains = s.contains("lo");
String replaced = s.replace('l', 'x');
    

This code uses common string methods like length, charAt, substring, contains, and replace.

repeat

Identify Repeating Operations

Look at which parts repeat or scan the string.

• Primary operation: Methods like replace and contains scan the string characters.
• How many times: They check each character once, so the number of checks grows with string length.

search_insights

How Execution Grows With Input

As the string gets longer, some methods take longer because they look at more characters.

Input Size (n)	Approx. Operations
10	About 10 checks for scanning methods
100	About 100 checks for scanning methods
1000	About 1000 checks for scanning methods

Pattern observation: The time grows roughly in direct proportion to the string length for scanning methods.

cards_stack

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows in a straight line as the string gets longer.

chat_error

Common Mistake

[X] Wrong: "All string methods run instantly no matter the string size."

[OK] Correct: Some methods check each character, so longer strings take more time.

business_center

Interview Connect

Knowing how string methods scale helps you write code that stays fast even with big text data.

psychology_alt

Self-Check

"What if we used indexOf instead of contains? How would the time complexity change?"