Strings in Java

Strings are a fundamental data type in Java and are widely used in Leetcode problems. Understanding their properties and operations is crucial for solving problems efficiently.

---

Table of Contents

1. String Basics
2. Common String Operations
3. StringBuilder and StringBuffer
4. Common Leetcode Patterns
5. Time and Space Complexity
6. Related Leetcode Questions

---

String Basics

• Definition: A string is a sequence of characters. In Java, strings are immutable (cannot be changed after creation).
• Declaration:

  String str = "Hello, World!";

• Immutable Nature: Any operation that modifies a string creates a new string object.

---

Common String Operations

1. Length of a String

• Method: length()
• Example:

  String str = "Hello";
  int len = str.length(); // len = 5

• Time Complexity: O(1)
• Space Complexity: O(1)

2. Accessing Characters

• Method: charAt(int index)
• Example:

  String str = "Hello";
  char ch = str.charAt(0); // ch = 'H'

• Time Complexity: O(1)
• Space Complexity: O(1)

3. Substring

• Method: substring(int start, int end)
• Example:

  String str = "Hello";
  String sub = str.substring(1, 3); // sub = "el"

• Time Complexity: O(n) (where n is the length of the substring)
• Space Complexity: O(n)

4. Concatenation

• Method: concat(String str) or + operator
• Example:

  String str = "Hello";
  String newStr = str.concat(" World"); // newStr = "Hello World"

• Time Complexity: O(n + m) (where n and m are lengths of the strings)
• Space Complexity: O(n + m)

5. Searching in a String

• Method: indexOf(String str)
• Example:

  String str = "Hello";
  int index = str.indexOf("el"); // index = 1

• Time Complexity: O(n * m) (worst case)
• Space Complexity: O(1)

6. Splitting a String

• Method: split(String regex)
• Example:

  String str = "Hello, World!";
  String[] parts = str.split(","); // parts = ["Hello", " World!"]

• Time Complexity: O(n)
• Space Complexity: O(n)

7. Trimming Whitespace

• Method: trim()
• Example:

  String str = "  Hello  ";
  String trimmed = str.trim(); // trimmed = "Hello"

• Time Complexity: O(n)
• Space Complexity: O(n)

8. Replacing Characters

• Method: replace(char oldChar, char newChar)
• Example:

  String str = "Hello";
  String replaced = str.replace('l', 'L'); // replaced = "HeLLo"

• Time Complexity: O(n)
• Space Complexity: O(n)

---

StringBuilder and StringBuffer

• StringBuilder: Mutable sequence of characters. Not thread-safe.
• StringBuffer: Mutable sequence of characters. Thread-safe.
• Common Methods:
  • append(String str)
  • insert(int offset, String str)
  • delete(int start, int end)
  • reverse()
• Example:

  StringBuilder sb = new StringBuilder("Hello");
  sb.append(" World"); // sb = "Hello World"

• Time Complexity:
  • Append: O(1) (amortized)
  • Insert/Delete: O(n)
• Space Complexity: O(n)

---

Common Leetcode Patterns

1. Two Pointers

• Used for problems like palindrome checking, reverse string, etc.
• Example:

  String str = "madam";
  int left = 0, right = str.length() - 1;
  while (left < right) {
      if (str.charAt(left) != str.charAt(right)) return false;
      left++;
      right--;
  }
  return true;

• Related Questions:
  • Valid Palindrome
  • Reverse String
  • Two Sum II - Input Array is Sorted

2. Sliding Window

• Used for problems like longest substring without repeating characters.
• Example:

  String str = "abcabcbb";
  int[] map = new int[128];
  int left = 0, right = 0, maxLen = 0;
  while (right < str.length()) {
      char c = str.charAt(right);
      map[c]++;
      while (map[c] > 1) {
          char leftChar = str.charAt(left);
          map[leftChar]--;
          left++;
      }
      maxLen = Math.max(maxLen, right - left + 1);
      right++;
  }

• Related Questions:
  • Longest Substring Without Repeating Characters
  • Minimum Window Substring
  • Permutation in String

3. String Manipulation

• Problems like anagram checking, group anagrams, etc.
• Example:

  String str1 = "anagram";
  String str2 = "nagaram";
  char[] arr1 = str1.toCharArray();
  char[] arr2 = str2.toCharArray();
  Arrays.sort(arr1);
  Arrays.sort(arr2);
  return Arrays.equals(arr1, arr2);

• Related Questions:
  • Valid Anagram
  • Group Anagrams
  • Find All Anagrams in a String

---

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Length (length())	O(1)	O(1)
Access (charAt())	O(1)	O(1)
Substring (substring())	O(n)	O(n)
Concatenation (+)	O(n + m)	O(n + m)
Search (indexOf())	O(n * m)	O(1)
Split (split())	O(n)	O(n)
Trim (trim())	O(n)	O(n)
Replace (replace())	O(n)	O(n)
StringBuilder Append	O(1) (amortized)	O(n)
StringBuilder Insert/Delete	O(n)	O(n)

---

Related Leetcode Questions

Easy

1. Valid Palindrome
2. Reverse String
3. Valid Anagram

Medium

1. Longest Substring Without Repeating Characters
2. Group Anagrams
3. Find All Anagrams in a String

Hard

1. Minimum Window Substring
2. Sliding Window Maximum
3. Longest Valid Parentheses