Learning Paths/Foundations/Strings

Strings

Strings are fundamental data structures that represent sequences of characters. This module covers the essential concepts, operations, and common patterns for working with strings.

Module Contents

Learning Resources

Introduction to Strings

A string is a sequence of characters. In most programming languages, strings are implemented as arrays of characters with special properties and methods.

Key Characteristics

Immutable in many languages (Java, Python, JavaScript)
Special operations like concatenation, substring, etc.
Often have built-in methods for common operations
Can be represented as character arrays in some languages

Common String Operations

Operation	Time Complexity	Description
Length	O(1)	Getting the length of a string
Concatenation	O(n+m)	Joining two strings
Substring	O(k)	Extracting a portion of the string
String Comparison	O(n)	Comparing two strings

String Implementation

Java Implementation

// String operations in Java
String str = "Hello, World!";

// String length
int length = str.length();  // Returns 13

// Accessing characters
char firstChar = str.charAt(0);  // Returns 'H'

// Substring
String sub = str.substring(0, 5);  // Returns "Hello"

// String concatenation
String newStr = str + " How are you?";  // Using + operator
String anotherStr = str.concat(" How are you?");  // Using concat method

// String comparison
boolean isEqual = str.equals("Hello, World!");  // Returns true
boolean isEqualIgnoreCase = str.equalsIgnoreCase("hello, world!");  // Returns true

// String searching
int index = str.indexOf("World");  // Returns 7
boolean contains = str.contains("Hello");  // Returns true

// String modification (creates new strings as Strings are immutable in Java)
String replaced = str.replace("Hello", "Hi");  // Returns "Hi, World!"
String upperCase = str.toUpperCase();  // Returns "HELLO, WORLD!"
String lowerCase = str.toLowerCase();  // Returns "hello, world!"
String trimmed = "  Hello  ".trim();  // Returns "Hello"

// Splitting strings
String[] parts = "apple,banana,orange".split(",");  // Returns ["apple", "banana", "orange"]

// StringBuilder for efficient string manipulation
StringBuilder sb = new StringBuilder();
sb.append("Hello");
sb.append(", ");
sb.append("World!");
String result = sb.toString();  // Returns "Hello, World!"

Python Implementation

# String operations in Python
s = "Hello, World!"

# String length
length = len(s)  # Returns 13

# Accessing characters
first_char = s[0]  # Returns 'H'

# Substring (slicing)
sub = s[0:5]  # Returns "Hello"

# String concatenation
new_str = s + " How are you?"  # Using + operator

# String comparison
is_equal = (s == "Hello, World!")  # Returns True
is_equal_ignore_case = (s.lower() == "hello, world!")  # Returns True

# String searching
index = s.find("World")  # Returns 7
contains = "Hello" in s  # Returns True

# String modification (creates new strings as Strings are immutable in Python)
replaced = s.replace("Hello", "Hi")  # Returns "Hi, World!"
upper_case = s.upper()  # Returns "HELLO, WORLD!"
lower_case = s.lower()  # Returns "hello, world!"
trimmed = "  Hello  ".strip()  # Returns "Hello"

# Splitting strings
parts = "apple,banana,orange".split(",")  # Returns ["apple", "banana", "orange"]

# Join strings
joined = ", ".join(["apple", "banana", "orange"])  # Returns "apple, banana, orange"

# String formatting
formatted = f"The answer is {42}"  # Returns "The answer is 42"
formatted_old = "The answer is {}".format(42)  # Returns "The answer is 42"

Common String Patterns

1. String Reversal

Reversing a string is a common operation in many string manipulation problems.

// Java implementation of string reversal
public String reverseString(String s) {
    char[] chars = s.toCharArray();
    int left = 0;
    int right = chars.length - 1;
    
    while (left < right) {
        // Swap characters
        char temp = chars[left];
        chars[left] = chars[right];
        chars[right] = temp;
        
        // Move pointers
        left++;
        right--;
    }
    
    return new String(chars);
}

2. Palindrome Check

Checking if a string reads the same forwards and backwards.

# Python implementation of palindrome check
def is_palindrome(s):
    # Remove non-alphanumeric characters and convert to lowercase
    s = ''.join(c.lower() for c in s if c.isalnum())
    
    # Check if the string equals its reverse
    return s == s[::-1]

# Alternative implementation using two pointers
def is_palindrome_two_pointers(s):
    # Remove non-alphanumeric characters and convert to lowercase
    s = ''.join(c.lower() for c in s if c.isalnum())
    
    left, right = 0, len(s) - 1
    
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    
    return True

3. Anagram Check

Determining if two strings contain the same characters in a different order.

// Java implementation of anagram check
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    
    int[] counter = new int[26]; // Assuming lowercase English letters
    
    // Count characters in s
    for (char c : s.toCharArray()) {
        counter[c - 'a']++;
    }
    
    // Decrement counts for characters in t
    for (char c : t.toCharArray()) {
        counter[c - 'a']--;
        // If character appears more times in t than in s
        if (counter[c - 'a'] < 0) {
            return false;
        }
    }
    
    return true;
}

Practice Problems

Apply your knowledge of strings by solving these carefully selected problems:

1. Valid Palindrome

Determine if a string is a palindrome, considering only alphanumeric characters and ignoring case.

EasyTwo PointersString

Solve this problem →

2. Valid Anagram

Given two strings, determine if one is an anagram of the other.

EasyHash TableString

Solve this problem →

3. Longest Substring Without Repeating Characters

Find the length of the longest substring without repeating characters.

MediumHash TableSliding Window

Solve this problem →

4. String to Integer (atoi)

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

MediumStringMath

Solve this problem →

Previous: Arrays Next: Linked Lists