Common String Methods & Their Complexity

JavaScript provides a rich set of built-in methods for working with strings. These methods allow you to perform various operations like changing case, finding substrings, extracting parts, and more. Remember from the previous lesson that strings are immutable, meaning all these methods return a new string rather than modifying the original.

Understanding the time complexity of these methods is important for writing efficient code, especially when dealing with large strings. Time complexity is often expressed using Big O notation, where N typically refers to the length of the string being operated on, and M refers to the length of a substring or pattern involved.

---

String Length: .length (Property)

While not a method, length is the most common property used with strings. It returns the number of characters in the string.

• Syntax: string.length
• Returns: A number.
• Time Complexity: O(1) - Accessing the length is a direct lookup, as it's typically stored as a property of the string object.

let greeting = "Hello World!";
console.log(greeting.length); // Output: 12

---

Case Conversion: .toUpperCase() and .toLowerCase()

These methods convert all characters in a string to uppercase or lowercase, respectively.

• Syntax: string.toUpperCase() / string.toLowerCase()
• Returns: A new string with all characters converted.
• Time Complexity: O(N) - The method must iterate through all N characters of the string to create the new converted string.

let text = "JavaScript";
console.log(text.toUpperCase()); // Output: "JAVASCRIPT"
console.log(text.toLowerCase()); // Output: "javascript"

---

Trimming Whitespace: .trim(), .trimStart(), .trimEnd()

These methods remove whitespace (spaces, tabs, newlines) from the beginning, end, or both ends of a string.

• .trim(): Removes whitespace from both ends.
• .trimStart(): Removes whitespace from the beginning only.
• .trimEnd(): Removes whitespace from the end only.
• Returns: A new string with whitespace removed.
• Time Complexity: O(N) - In the worst case (e.g., a string full of leading/trailing spaces), the method might iterate through a significant portion of the string. A new string is always created.

let padded = "   Hello World   ";
console.log(padded.trim());      // Output: "Hello World"
console.log(padded.trimStart()); // Output: "Hello World   "
console.log(padded.trimEnd());   // Output: "   Hello World"

---

Finding Substrings: .indexOf(), .lastIndexOf(), .includes()

These methods help you locate or check for the presence of a substring within a string.

.indexOf()

Returns the index of the first occurrence of a specified substring. If the substring is not found, it returns -1. An optional second argument specifies the starting index for the search.

• Syntax: string.indexOf(substring, [startIndex])
• Returns: A number (index) or -1.
• Time Complexity: In the worst case, naive substring search is O(N * M) where N is the length of the main string and M is the length of the substring. Modern JavaScript engines use optimized algorithms (e.g., Boyer-Moore, Rabin-Karp) that often achieve near O(N + M) or average O(N) performance, but the theoretical worst case remains O(N * M).

let sentence = "The quick brown fox jumps over the lazy fox.";
console.log(sentence.indexOf("fox"));     // Output: 16 (first 'fox')
console.log(sentence.indexOf("fox", 20)); // Output: 40 (search starts from index 20)
console.log(sentence.indexOf("cat"));     // Output: -1

.lastIndexOf()

Returns the index of the last occurrence of a specified substring. Similar to indexOf(), but searches backward from the end (or from startIndex backward).

• Syntax: string.lastIndexOf(substring, [startIndex])
• Returns: A number (index) or -1.
• Time Complexity: Worst case O(N * M), similar reasoning as .indexOf().

let sentence = "The quick brown fox jumps over the lazy fox.";
console.log(sentence.lastIndexOf("fox"));      // Output: 40 (last 'fox')
console.log(sentence.lastIndexOf("fox", 30));  // Output: 16 (search ends at index 30)

.includes()

Checks if a string contains a specified substring. It's case-sensitive.

• Syntax: string.includes(substring, [startIndex])
• Returns: A boolean (true or false).
• Time Complexity: Worst case O(N * M), as it performs a substring search similar to .indexOf().

let phrase = "JavaScript is fun!";
console.log(phrase.includes("Script"));  // Output: true
console.log(phrase.includes("script"));  // Output: false (case-sensitive)
console.log(phrase.includes("is", 10));  // Output: false (starts searching from index 10)

---

Checking Start/End: .startsWith(), .endsWith()

These methods check if a string begins or ends with a specified substring.

• .startsWith(substring, [position]): Checks if the string starts with substring. position (optional) specifies where the search should begin within the string.
• .endsWith(substring, [length]): Checks if the string ends with substring. length (optional) can be used to treat the string as if it were shorter than its actual length.
• Returns: A boolean.
• Time Complexity: O(M), where M is the length of the substring, since only up to M characters need to be compared at the start or end.

let filename = "document.pdf";
console.log(filename.startsWith("doc"));     // Output: true
console.log(filename.endsWith(".pdf"));      // Output: true
console.log(filename.startsWith("ment", 4)); // Output: true (starts checking from index 4)

---

Extracting Substrings: .slice(), .substring(), .substr()

These methods extract a portion of a string and return it as a new string. They differ slightly in how they handle arguments.

.slice()

Extracts characters from startIndex up to (but not including) endIndex. Supports negative indices (counts from the end of the string).

• Syntax: string.slice(startIndex, [endIndex])
• Returns: A new string.
• Time Complexity: O(K), where K is the length of the new string being created, since it involves copying K characters into a new memory location.

let greeting = "Hello World!";
console.log(greeting.slice(0, 5));   // Output: "Hello"
console.log(greeting.slice(6));      // Output: "World!" (from index 6 to end)
console.log(greeting.slice(-6));     // Output: "World!" (last 6 characters)
console.log(greeting.slice(0, -7));  // Output: "Hello"

.substring()

Similar to slice(), but treats negative indices as 0 and swaps startIndex and endIndex if startIndex is greater than endIndex.

• Syntax: string.substring(startIndex, [endIndex])
• Returns: A new string.
• Time Complexity: O(K), where K is the length of the new string being created, similar to .slice().

let greeting = "Hello World!";
console.log(greeting.substring(0, 5));   // Output: "Hello"
console.log(greeting.substring(6, 11));  // Output: "World"
console.log(greeting.substring(11, 6));  // Output: "World" (arguments swapped internally)
console.log(greeting.substring(-5, 5));  // Output: "Hello" (negative treated as 0)

.substr() (Deprecated)

Extracts length characters from startIndex. It's considered a legacy feature and not recommended for new code.

• Syntax: string.substr(startIndex, [length])
• Returns: A new string.
• Time Complexity: O(K), where K is the length of the new string being created.

let greeting = "Hello World!";
console.log(greeting.substr(0, 5));  // Output: "Hello"
console.log(greeting.substr(6, 5));  // Output: "World"
console.log(greeting.substr(6));     // Output: "World!" (from index 6 to end)

Note: While you might encounter .substr() in older codebases, it's recommended to use .slice() or .substring() for new development.

---

Replacing Content: .replace(), .replaceAll()

These methods allow you to replace parts of a string.

.replace()

Replaces the first occurrence of a specified substring (or a pattern matched by a regular expression) with another string.

• Syntax: string.replace(searchValue, replaceValue)

• Returns: A new string.

• Time Complexity:

  • For searchValue as a string: Worst-case O(N * M) for substring search, plus time to build the result string.
  • For searchValue as a regular expression: Complexity depends on the regex; simple patterns often run in O(N), but complex patterns can be higher.

let text = "Dog Cat Dog";
console.log(text.replace("Dog", "Fox"));     // Output: "Fox Cat Dog" (only first 'Dog' replaced)
console.log(text.replace(/Dog/g, "Fox"));    // Output: "Fox Cat Fox" (using regex for all 'Dog')

.replaceAll()

Replaces all occurrences of a specified substring with another string. (Introduced in ES2021.)

• Syntax: string.replaceAll(searchValue, replaceValue)
• Returns: A new string.
• Time Complexity: Worst-case O(N * M) for substring search plus time to build the new string. For regex searchValue, complexity depends on the pattern.

let text = "Dog Cat Dog";
console.log(text.replaceAll("Dog", "Fox")); // Output: "Fox Cat Fox"

---

Splitting Strings: .split()

Divides a string into an ordered list of substrings, puts these substrings into an array, and returns the array.

• Syntax: string.split([separator], [limit])

• Returns: An array of strings.

• Time Complexity:

  • If separator is a single character: O(N) to iterate through the string.
  • If separator is a substring or a regex: Worst-case O(N * M) due to repeated substring searches, plus overhead of creating the new array and its substrings.

let sentence = "This is a sample sentence";
console.log(sentence.split(" "));    // Output: ["This", "is", "a", "sample", "sentence"]
console.log(sentence.split("s"));    // Output: ["Thi", " i", " a ", "ample ", "entence"]
console.log(sentence.split(" ", 3)); // Output: ["This", "is", "a"] (limit to 3 elements)
console.log("hello".split(""));      // Output: ["h", "e", "l", "l", "o"]

---

Accessing Characters: .charAt(), Bracket Notation []

You can access individual characters of a string by their index.

.charAt()

Returns the character at the specified index.

• Syntax: string.charAt(index)
• Returns: A string (the character) or an empty string if index is out of bounds.
• Time Complexity: O(1) - Direct access to the character at a given index.

let word = "JavaScript";
console.log(word.charAt(0));  // Output: "J"
console.log(word.charAt(4));  // Output: "S"
console.log(word.charAt(10)); // Output: "" (empty string, out of bounds)

Bracket Notation []

Provides a more concise way to access characters by index. If the index is out of bounds, it returns undefined.

• Syntax: string[index]
• Returns: A string (the character) or undefined if index is out of bounds.
• Time Complexity: O(1) - Direct access to the character at a given index.

let word = "JavaScript";
console.log(word[0]);  // Output: "J"
console.log(word[4]);  // Output: "S"
console.log(word[10]); // Output: undefined (out of bounds)

---

Concatenating Strings: .concat(), + Operator

These methods/operators combine two or more strings into a single new string. The + operator is generally more commonly used and preferred for readability.

.concat()

• Syntax: string1.concat(string2, [string3, ...])
• Returns: A new string.
• Time Complexity: O(N + M) (or O(L) where L is the total length of the resulting string) since a new string is created and all characters must be copied.

let str1 = "Hello";
let str2 = "World";
console.log(str1.concat(" ", str2, "!")); // Output: "Hello World!"

+ Operator (Concatenation Operator)

The most common way to concatenate strings.

• Syntax: string1 + string2
• Returns: A new string.
• Time Complexity: O(N + M) - Similar to .concat(). Note that repeated concatenation in a loop can lead to O(N^2) behavior if building up a large string piece by piece.

let firstName = "John";
let lastName = "Doe";
let fullName = firstName + " " + lastName;
console.log(fullName); // Output: "John Doe"

---

Practical Application: String Reversal

Since there is no built-in string.reverse() method in JavaScript, this is a classic programming challenge that requires us to combine the fundamental concepts we've just learned. The key is to remember that strings are immutable, so we must build a new string.

Here are two common and efficient ways to reverse a string:

Method 1: Looping Backwards

This is often the most direct and efficient method. We iterate through the original string from the last character to the first, and append each character to a new string.

• Concept: Start at the last index (string.length - 1) and loop down to index 0.
• Tools Used: string.length, bracket notation ([]), + operator.
• Time Complexity: O(N) - We visit each character of the string exactly once.
• Space Complexity: O(N) - We create a new string of the same length as the original.

function reverseString(str) {
  // Initialize an empty string to build the reversed string
  let reversedString = "";

  // Loop from the last character to the first
  for (let i = str.length - 1; i >= 0; i--) {
    // Append the character at the current index to the new string
    reversedString += str[i];
  }

  // Return the new reversed string
  return reversedString;
}

// Example usage:
console.log(reverseString("hello"));       // Output: "olleh"
console.log(reverseString("JavaScript"));  // Output: "tpircSavaJ"
console.log(reverseString("  abc  "));     // Output: "  cba  "

Method 2: Using split(), join(), and Array Methods

This is a very common and readable approach that leverages the ability to convert a string to an array.

• Concept: Convert the string into an array of characters, reverse the array (since arrays are mutable and have a reverse() method), and then join the array back into a string.
• Tools Used: .split(), Array.prototype.reverse(), .join().
• Time Complexity: O(N) - All three steps (split, reverse, join) iterate through the elements, resulting in a linear time complexity.
• Space Complexity: O(N) - A new array of characters is created.

function reverseStringWithSplit(str) {
  // 1. Split the string into an array of characters
  const charArray = str.split(""); // separator is an empty string, so each character becomes an element

  // 2. Reverse the array in place
  charArray.reverse();

  // 3. Join the characters back into a new string
  const reversedString = charArray.join("");

  return reversedString;
}

// Example usage:
console.log(reverseStringWithSplit("hello"));       // Output: "olleh"
console.log(reverseStringWithSplit("JavaScript"));  // Output: "tpircSavaJ"
console.log(reverseStringWithSplit("  abc  "));     // Output: "  cba  "

Note: While the split() and join() method is very concise, the first method (looping) is often presented in a DSA context as it forces a deeper understanding of iteration and building data structures from scratch, without relying on a pre-built utility like Array.prototype.reverse(). The challenge in the next section will ask you to solve it this way!