Common string methods in Java - Time & Space Complexity

Time Complexity: Common string methods

O(n)

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?

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.

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.

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.

Final Time Complexity

Time Complexity: O(n)

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

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.

Interview Connect

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

Self-Check

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

Practice

1. Which Java String method checks if a string contains a specific sequence of characters?

easy

A. equals()

B. contains()

C. substring()

D. replace()

Solution

1. Step 1: Understand the purpose of contains()

   The contains() method checks if the string includes a specific sequence of characters and returns true or false.

2. Step 2: Compare with other methods

   equals() checks full equality, substring() extracts part of a string, and replace() changes characters. None check for containment.

3. Final Answer:

   contains() -> Option B

4. Quick Check:

   Check substring presence = contains() [OK]

Hint: Use contains() to check if text is inside a string [OK]

Common Mistakes:

• Confusing contains() with equals()
• Using substring() to check presence
• Thinking replace() checks for text

2. Which of the following is the correct syntax to convert a string str to uppercase in Java?

easy

A. str.toUpperCase();

B. str.uppercase();

C. toUpperCase(str);

D. str.toUpper();

Solution

1. Step 1: Recall the method name for uppercase conversion

   The correct method name in Java String class is toUpperCase(), called on the string object.

2. Step 2: Check syntax correctness

   str.toUpperCase(); uses str.toUpperCase(); which is valid. Others use incorrect method names or syntax.

3. Final Answer:

   str.toUpperCase(); -> Option A

4. Quick Check:

   Uppercase method = toUpperCase() [OK]

Hint: Remember Java String methods use camelCase like toUpperCase() [OK]

Common Mistakes:

• Using uppercase() instead of toUpperCase()
• Calling method without object (toUpperCase(str))
• Using toUpper() which does not exist

3. What is the output of the following Java code?

String text = "Hello World";
int pos = text.indexOf("World");
System.out.println(pos);

medium

A. 6

B. 0

C. -1

D. 5

Solution

1. Step 1: Understand what indexOf() does

   The indexOf() method returns the starting index of the substring if found, or -1 if not found.

2. Step 2: Find the position of "World" in "Hello World"

   "Hello " has 6 characters (index 0 to 5), so "World" starts at index 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Substring start index = 6 [OK]

Hint: indexOf() returns first position of substring or -1 if missing [OK]

Common Mistakes:

• Confusing index with length
• Expecting index 0 for substring
• Thinking indexOf() returns boolean

4. Identify the error in this Java code snippet:

String s = "Java Programming";
String part = s.substring(5, 3);
System.out.println(part);

medium

A. substring() cannot be used on String objects

B. Missing semicolon after substring() call

C. substring() arguments are reversed; start index must be <= end index

D. The variable 'part' is not declared

Solution

1. Step 1: Check substring() method argument rules

   substring(start, end) requires start index less than or equal to end index; here 5 > 3, which is invalid.

2. Step 2: Confirm other syntax correctness

   Semicolons are present, substring() is valid on String, and 'part' is declared properly.

3. Final Answer:

   substring() arguments are reversed; start index must be <= end index -> Option C

4. Quick Check:

   substring(start, end) needs start ≤ end [OK]

Hint: Start index must not be greater than end index in substring() [OK]

Common Mistakes:

• Swapping start and end indexes
• Thinking substring() changes original string
• Ignoring exception thrown at runtime

5. Given the string input = "apple,banana,orange", which code snippet correctly replaces all commas with semicolons and converts the result to uppercase?

hard

A. input.replaceFirst(",", ";").toUpperCase();

B. input.toUpperCase().replaceFirst(",", ";");

C. input.replace(",", ";").toUpper();

D. input.replaceAll(",", ";").toUpperCase();

Solution

1. Step 1: Understand replace() vs replaceAll()

   Both replace() and replaceAll() can replace characters, but replaceAll() uses regex and is safer for multiple replacements.

2. Step 2: Check method chaining and correctness

   A and B use replaceFirst() which only replaces the first comma. C uses invalid toUpper().

3. Step 3: Choose best practice

   Using replaceAll() with chaining to toUpperCase() is correct and clear.

4. Final Answer:

   input.replaceAll(",", ";").toUpperCase(); -> Option D

5. Quick Check:

   Replace commas then uppercase = replaceAll + toUpperCase() [OK]

Hint: Chain replaceAll() then toUpperCase() for clean transformation [OK]

Common Mistakes:

• Using toUpper() instead of toUpperCase()
• Using replaceFirst() which only replaces the first occurrence
• Confusing replace() and replaceAll() usage