String Data Structure: Mutable/Immutable Strings, Pattern Matching, and Palindrome (2026)
A string is a sequence of characters used to represent text. Strings are one of the most commonly used data types in programming. Different languages treat strings differently — C++ strings are mutable, Java strings are immutable, and Python strings are also immutable. Understanding these differences is crucial for writing efficient code.
This tutorial covers substring operations, pattern matching (naive and KMP), palindrome checking, and string reversal. Code examples in C++, Java, and Python demonstrate the concepts across each language's string paradigm.
Mutable vs Immutable Strings and Substring Operations
C++ std::string is mutable — you can change individual characters with str[i] = 'a';. Java's String is immutable — any modification creates a new string; use StringBuilder for mutable operations. Python strings are also immutable; use list(str) for mutation or string slicing for extraction.
Substring extraction: C++ s.substr(pos, len), Java s.substring(begin, end), Python s[start:end]. All create new strings (or views in C++17). Concatenation performance varies — Java StringBuilder and Python ''.join() are O(n); repeated += can be O(n^2).
// C++
string s = "hello";
s[0] = 'H'; // mutable
string sub = s.substr(0, 4); // "Hell"
// Java
String s = "hello";
// s[0] = 'H'; // error: immutable
StringBuilder sb = new StringBuilder(s);
sb.setCharAt(0, 'H');
String sub = s.substring(0, 4); // "hell"
// Python
s = "hello"
# s[0] = 'H' # error: immutable
lst = list(s); lst[0] = 'H'; s = "".join(lst)
sub = s[:4] # "hell"Pattern Matching: Naive and KMP Algorithm
The naive pattern-matching algorithm slides the pattern over the text one position at a time and compares each character. Worst-case time is O(m * n), where m is the text length and n is the pattern length. The Knuth-Morris-Pratt (KMP) algorithm improves this to O(m + n) by preprocessing the pattern to compute a failure (LPS) array.
The LPS array (longest proper prefix which is also a suffix) tells the algorithm how many characters can be skipped after a mismatch. When a mismatch occurs, the pattern shifts by j - lps[j-1] positions instead of restarting from the beginning. KMP is especially efficient when the pattern contains repeating substrings.
// C++ — KMP
void computeLPS(string pat, vector& lps) {
int len=0, i=1;
while(i < pat.size()) {
if(pat[i] == pat[len]) lps[i++] = ++len;
else if(len) len = lps[len-1];
else lps[i++] = 0;
}
}
// Java — KMP
// Same algorithm with char arrays
// Python — KMP
def kmp_search(text, pat):
lps = [0] * len(pat)
j = 0
for i in range(1, len(pat)):
while j and pat[i] != pat[j]: j = lps[j-1]
if pat[i] == pat[j]: j += 1; lps[i] = j
j = 0
for i in range(len(text)):
while j and text[i] != pat[j]: j = lps[j-1]
if text[i] == pat[j]: j += 1
if j == len(pat): return i - j + 1 Palindrome and String Reversal
A palindrome is a string that reads the same forwards and backwards. To check, compare the string with its reverse or use two pointers from both ends moving inward. Common palindrome variants include case-insensitive, ignoring non-alphanumeric characters (e.g., 'A man, a plan, a canal: Panama').
String reversal can be done with built-in functions (reverse() in C++, StringBuilder.reverse() in Java, [::-1] in Python) or manually with a two-pointer swap. The two-pointer approach runs in O(n) time and O(1) space if the string is mutable.
// C++
bool isPalindrome(string s) {
int l=0, r=s.size()-1;
while(lFrequently Asked Questions
What is the difference between String and StringBuilder in Java?
String is immutable (thread-safe, cached). StringBuilder is mutable (faster for repeated modifications but not thread-safe).
Why is KMP more efficient than naive pattern matching?
KMP avoids re-examining matched characters by using the LPS array to skip unnecessary comparisons, achieving O(m + n) vs O(m * n).
Originally published on Ayodhyyya. Last updated June 1, 2026.