# 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. |