Strings are a fundamental data structure. They are particularly important in areas such as text processing, parsing, and algorithm design. Here’s an overview of strings and their common operations:

Definition and Characteristics

  • Sequence of Characters: A string is a sequence of characters, typically stored in contiguous memory locations.
  • Immutable or Mutable: Depending on the programming language, strings can be immutable (cannot be changed once created, as in Java and Python) or mutable (can be modified, as in C++ or Ruby).
  • Indexed: Characters in a string can be accessed by their index, with indexing usually starting from 0.
graph TD;
    subgraph String
    0((0)) --> A["h"]
    1((1)) --> B["e"]
    2((2)) --> C["l"]
    3((3)) --> D["l"]
    4((4)) --> E["o"]
    5((5)) --> F[" "]
    6((6)) --> G["w"]
    7((7)) --> H["o"]
    8((8)) --> I["r"]
    9((9)) --> J["l"]
    10((10)) --> K["d"]

Common String Operations

  • Accessing Characters: Accessing a character at a specific index is typically an O(1) operation.
  • Concatenation: Joining two strings together. The time complexity can vary but is often O(n + m), where n and m are the lengths of the strings.
  • Substrings: Extracting a substring can typically be done in O(n) time.
  • Search: Searching for a character or substring, such as with the indexOf method in Java, is generally an O(n) operation.
  • Comparison: Comparing two strings can be done in O(n) time, where n is the length of the shorter string.

BigO of common operations

Operation Time Complexity Comments
Accessing a Character O(1) Accessing characters by index is typically constant time.
Concatenation O(n + m) Concatenating two strings of length n and m. Can be less efficient in languages where strings are immutable.
Substring O(n) Extracting a substring can be linear in the size of the substring.
Searching for a Character O(n) Linear search is required in an unsorted string.
Searching for a Substring O(n*m) Worst-case scenario when searching for a substring of length m in a string of length n. Optimized algorithms like KMP, Rabin-Karp, or Z-algorithm can be faster.
Length of a String O(1) or O(n) Typically O(1), but can be O(n) if the language does not store the length as a property of the string.
Comparison O(n) In the worst case, comparing each character of strings of length n.
Trimming Spaces (if applicable) O(n) Removing spaces from the beginning and/or end of the string requires scanning the string.
Splitting a String O(n) Depends on the number of splits and the length of the string.
Replacing Characters O(n) Assuming a simple character-by-character replacement in a string of length n.