Back to Study Material Data Structures and Algorithms

Strings

A string is a sequence of characters. In most programming languages, strings are stored as arrays of characters in contiguous memory, terminated by a senti...

Strings

Character Sequences, Immutability, and Fundamental String Operations

A string is a sequence of characters. In most programming languages, strings are stored as arrays of characters in contiguous memory, terminated by a sentinel value (as in C) or accompanied by a length field (as in Python or Java). The choice of internal representation affects performance characteristics for common operations.

Character access by index is O(1) in languages that store strings as arrays. Computing the length of a string is O(1) when the length is stored alongside the characters, but O(n) in C-style null-terminated strings because the runtime must scan until it finds the null terminator.

String concatenation is a subtle source of performance bugs. In languages where strings are immutable, such as Java and Python, concatenating two strings creates a new string object and copies both character sequences. Concatenating n strings one at a time in a loop produces a total copy count of 0 plus 1 plus 2 plus ... plus (n minus one), which is O(n^2). The fix is to accumulate pieces in a list and join them at the end, reducing concatenation to O(total length).

String comparison checks whether two strings are equal character by character. In the worst case, both strings are identical and all n characters must be checked, giving O(n) time. Comparing by length first can short-circuit quickly when lengths differ.

Substrings and slicing create a view into a portion of the original string. In languages like Go, slices share the underlying array with the original string, making slicing O(1) but requiring care around mutations. In Python, string slicing creates a new string, costing O(k) where k is the length of the slice.

Common string problems: reversing a string, checking for palindromes, finding the first non-repeating character, checking for anagrams, and compressing a string by replacing repeated characters with a count. A palindrome check requires comparing the string to its reverse or using two pointers meeting in the middle, both O(n).

Anagram detection: two strings are anagrams if they contain the same characters with the same frequencies. Sort both strings and compare: O(n log n). Alternatively, build a frequency map for one string and decrement it for the other: O(n) time and O(1) space if the character set is fixed size (say, 26 lowercase letters).

Worked example: given a string, find the length of its longest palindromic substring. A brute force checks all O(n^2) substrings, each check O(n), giving O(n^3). The expand-around-center approach considers each character (and each pair of adjacent characters) as a potential palindrome center and expands outward, giving O(n^2) time and O(1) space. Manacher's algorithm solves it in O(n).

Interview tip: clarify the character set at the start of any string problem. Is it only lowercase letters, all ASCII, or full Unicode? The answer affects which algorithms and data structures (fixed-size arrays versus hash maps) are appropriate.