Strings

Understanding strings as a data structure.

What are Strings?

A string is a sequence of characters. Unlike arrays, which hold homogeneous data (like integers or floats), strings are specifically designed for handling characters. Strings are immutable in many programming languages, meaning once you create a string, you can’t change its content directly.

Types of Strings

  1. Mutable Strings: These are strings that can be modified after creation. Languages like C++ (with char arrays) allow direct modification of string contents.

  2. Immutable Strings: These are strings that can’t be changed after creation. Languages like Python and Java use this approach, which can be frustrating at first but helps with performance and security.

  3. String Builders/Buffers: These are special string types that allow efficient string modifications without creating new string objects each time.

How Strings Are Stored

Let’s talk memory. In most languages, strings are stored as a continuous block of characters. For example:

  • In C++, a string often ends with a null character ('\0') to mark where it stops.
  • In Python and Java, these details are abstracted—just remember strings are immutable in these languages.

When you think about memory, imagine a bookshelf where each slot represents a character in the string. If I have a string like "Hello", it’s stored as contiguous slots with H, e, l, l, and o. That’s why accessing the third letter is super fast—because it knows exactly where it is!

Common String Operations

  • Basic Operations

    • Access character at index: O(1)
    • Find length: O(1)
    • Get substring: O(n)

  • Modification Operations

    • Concatenation: O(n+m)
    • Replace/Delete: O(n)
    • Reverse: O(n)

Code Examples

Here’s how you work with strings in C++, Python, and Java. Each language has its own syntax, but once you understand one, switching between them isn’t that hard.

# Defining a string
str = "Hello, World!"

# String length
print("Length:", len(str))

# Concatenation
greeting = str + " How are you?"
print("Concatenated:", greeting)

# Substring
print("Substring:", str[7:12])

# Searching for a character
pos = str.find('W')
if pos != -1:
    print("'W' found at position:", pos)
  • KMP (Knuth-Morris-Pratt)
  • Rabin-Karp
  • Z Algorithm
  • Manacher's Algorithm

Problems to Solve

Important Problems on Strings

Resources