Strings

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"]
    end

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.