Strings
A string is a sequence of characters used to represent text.
Examples:
"Uday" "Hello World" "Computer Science" "12345" "Hello@123"
In DSA, strings are important because many real-world problems involve text processing, searching, comparison, manipulation, and pattern matching.
1. What Is a Character?
Before understanding strings, understand a character.
A character is a single symbol.
Examples:
'A' 'b' '7' '@' ' '
In C++:
char ch = 'A';
A char stores one character.
A string contains multiple characters:
"HELLO"
Conceptually:
H E L L O
2. What Is a String?
A string is a sequence of characters.
For example:
"HELLO"
can be viewed as:
Index: 0 1 2 3 4 ┌───┬───┬───┬───┬───┐ Value: │ H │ E │ L │ L │ O │ └───┴───┴───┴───┴───┘
Just like arrays, string indexing normally starts from 0.
Therefore:
str[0] = H str[1] = E str[2] = L str[3] = L str[4] = O
This is why strings and arrays are closely related.
3. Strings in C++
There are two major ways you will encounter strings in C++:
1. C-style strings
char name[] = "Uday";
2. std::string
string name = "Uday";
For modern C++ DSA programming, you will usually use:
string
because it is easier and safer to work with.
4. Creating a String
You can write:
#include <iostream> #include <string> using namespace std; int main() { string name = "Uday"; cout << name; return 0; }
Output:
Uday
5. String Indexing
Consider:
string name = "Uday";
The characters are:
Index: 0 1 2 3 ┌────┬────┬────┬────┐ │ U │ d │ a │ y │ └────┴────┴────┴────┘
Access:
cout << name[0];
Output:
U
And:
cout << name[2];
Output:
a
6. Changing a Character
Strings can be modified.
string name = "Uday"; name[0] = 'B'; cout << name;
Output:
Bday
So:
Before: U d a y After: B d a y
7. Finding String Length
Use:
string name = "Uday"; cout << name.length();
Output:
4
You can also use:
name.size()
Example:
cout << name.size();
Both are commonly used.
8. Traversing a String
You can process every character using a loop.
string name = "Uday"; for(int i = 0; i < name.length(); i++) { cout << name[i] << endl; }
Output:
U d a y
Complexity:
Time = O(n)
where n is the length of the string.
9. Taking String Input
There are two common methods.
Using cin
string name; cin >> name;
If input is:
Uday
it works.
But cin stops at whitespace.
For example:
Uday Raut
only:
Uday
would be read.
10. Using getline()
To read a complete line:
string name; getline(cin, name);
Input:
Uday Raut
Output:
Uday Raut
So remember:
cin → reads one word getline → reads an entire line
11. Concatenation
Concatenation means joining strings together.
Example:
string first = "Uday"; string last = "Raut"; string full = first + " " + last; cout << full;
Output:
Uday Raut
Here:
"Uday" + " " + "Raut"
becomes:
"Uday Raut"
12. Comparing Strings
You can compare strings using:
==
Example:
string a = "hello"; string b = "hello"; if(a == b) { cout << "Same"; }
Output:
Same
Different strings:
string a = "hello"; string b = "world"; if(a == b) { cout << "Same"; } else { cout << "Different"; }
Output:
Different
13. Lexicographical Comparison
Strings can also be compared alphabetically.
For example:
"apple" "banana"
Alphabetically:
apple < banana
In C++:
string a = "apple"; string b = "banana"; if(a < b) { cout << "a comes first"; }
This type of comparison is called lexicographical comparison.
It is similar to how words are ordered in a dictionary.
14. Adding Characters
You can add a character using:
string s = "Hello"; s += '!'; cout << s;
Output:
Hello!
You can also concatenate:
s += " World";
Now:
Hello! World
15. Removing the Last Character
You can use:
string s = "Hello"; s.pop_back(); cout << s;
Output:
Hell
pop_back() removes the final character.
16. Adding at the End
Use:
s.push_back('!');
Example:
string s = "Hello"; s.push_back('!'); cout << s;
Output:
Hello!
17. Accessing the Last Character
You can use:
string s = "Hello"; cout << s.back();
Output:
o
Similarly:
s.front()
returns the first character.
cout << s.front();
Output:
H
18. Substring
A substring is a part of a string.
Suppose:
"Computer"
Some substrings are:
"Comp" "put" "ter" "Computer"
In C++:
string s = "Computer"; cout << s.substr(0, 4);
Output:
Comp
The syntax is:
s.substr(start, length)
So:
substr(0, 4)
means:
Start at index 0 Take 4 characters
19. Finding a Substring
Suppose:
string s = "I love programming";
We want to find:
"programming"
Use:
size_t pos = s.find("programming");
If found, it returns its starting position.
You can write:
if(s.find("programming") != string::npos) { cout << "Found"; }
Output:
Found
If it isn't found, find() returns:
string::npos
20. Reversing a String
Suppose:
"hello"
We want:
"olleh"
You can use:
#include <algorithm> reverse(s.begin(), s.end());
Example:
string s = "hello"; reverse(s.begin(), s.end()); cout << s;
Output:
olleh
21. Reversing Manually
For DSA, you should also understand how to reverse a string without using a built-in function.
string s = "hello"; int left = 0; int right = s.length() - 1; while(left < right) { swap(s[left], s[right]); left++; right--; }
Conceptually:
Before: h e l l o ↑ ↑ L R Swap: o e l l h ↑ ↑ Continue: o l l e h
Result:
olleh
Complexity:
Time = O(n) Space = O(1)
This is an important two-pointer technique.
22. Checking Palindrome
A palindrome is a string that reads the same forward and backward.
Examples:
madam level racecar 121
Not palindrome:
hello computer uday
Example:
"madam" Forward: m a d a m Backward: m a d a m
They are the same.
23. Palindrome Algorithm
Using two pointers:
string s = "madam"; int left = 0; int right = s.length() - 1; bool palindrome = true; while(left < right) { if(s[left] != s[right]) { palindrome = false; break; } left++; right--; } if(palindrome) { cout << "Palindrome"; } else { cout << "Not Palindrome"; }
Complexity:
Time = O(n) Space = O(1)
24. Counting Characters
Suppose:
"hello"
We want to count how many times 'l' appears.
string s = "hello"; int count = 0; for(char ch : s) { if(ch == 'l') { count++; } } cout << count;
Output:
2
Complexity:
O(n)
25. Counting Vowels
We can count:
a e i o u
Example:
string s = "computer"; int count = 0; for(char ch : s) { if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') { count++; } } cout << count;
Output:
3
Because:
computer ↑ ↑ ↑ o u e
26. Uppercase and Lowercase
C++ provides functions such as:
toupper() tolower()
Example:
char ch = 'a'; cout << char(toupper(ch));
Output:
A
And:
char ch = 'A'; cout << char(tolower(ch));
Output:
a
For an entire string:
for(char &ch : s) { ch = toupper(ch); }
27. String and ASCII
Characters are internally represented using numeric character codes.
For example, ASCII includes:
'A' → 65 'B' → 66 'C' → 67 ... 'a' → 97 'b' → 98
So:
char ch = 'A'; cout << int(ch);
produces:
65
This becomes useful in many DSA problems involving character frequency and transformations.
28. Character Frequency
One of the most common string problems is:
Count how many times each character occurs.
Example:
"banana"
Frequency:
b → 1 a → 3 n → 2
For lowercase English letters, you can use an array:
int freq[26] = {0}; for(char ch : s) { freq[ch - 'a']++; }
Why?
For:
'a'
we get:
'a' - 'a' = 0
For:
'b'
we get:
'b' - 'a' = 1
So:
a → index 0 b → index 1 c → index 2 ... z → index 25
This is a very important connection between arrays and strings.
29. String as an Array of Characters
Conceptually:
string s = "hello";
can be thought of as:
Index: 0 1 2 3 4 ↓ ↓ ↓ ↓ ↓ h e l l o
Therefore many array techniques work on strings:
- Traversal
- Two pointers
- Searching
- Frequency counting
- Sorting
- Reversing
This is why learning arrays first was important.
30. Important String Complexity
For a string of length n:
| Operation | Typical Complexity |
|---|---|
| Access character by index | O(1) |
| Update character | O(1) |
| Traverse | O(n) |
| Find character manually | O(n) |
| Compare two strings | O(n) worst case |
| Reverse | O(n) |
| Count characters | O(n) |
Find substring using basic find | Depends on implementation/pattern; don't assume O(1) |
For DSA, always consider the string length when analyzing an operation.
31. String vs Character
This distinction is important.
Character
char ch = 'A';
One character.
String
string s = "A";
A sequence containing one character.
Notice:
'A' → character "A" → string
Single quotes:
'A'
Double quotes:
"A"
32. C-Style String
You may also encounter:
char name[] = "Uday";
Internally, a C-style string ends with a special character:
'\0'
So conceptually:
U d a y \0
The null character tells C-style string functions where the string ends.
For modern C++ DSA, however, you will generally prefer:
string name = "Uday";
33. Common String Problems
After learning the basics, you should practice:
Beginner
- Find string length
- Print each character
- Count vowels
- Count consonants
- Count digits
- Convert uppercase/lowercase
- Reverse a string
- Check palindrome
Intermediate
- Count frequency of characters
- Find first non-repeating character
- Remove duplicate characters
- Check whether two strings are anagrams
- Find the most frequent character
- Reverse words
- Count words
- Check whether one string is a rotation of another
Advanced
- Pattern matching
- Longest substring problems
- Sliding window
- Prefix-based techniques
- String hashing
- KMP
- Z algorithm
- Trie-based string problems
Some of these techniques will appear later in your DSA journey.
34. Example: Anagram
Two strings are anagrams if they contain the same characters with the same frequencies, possibly in a different order.
Example:
"listen" "silent"
Both contain:
l → 1 i → 1 s → 1 t → 1 e → 1 n → 1
Therefore:
listen ↔ silent
They are anagrams.
A frequency array can solve many such problems efficiently.
35. Example: Remove Spaces
Suppose:
"hello world"
We want:
"helloworld"
One approach:
string result; for(char ch : s) { if(ch != ' ') { result += ch; } }
This demonstrates a common pattern:
Input string ↓ Process each character ↓ Build result
36. Strings and DSA
Strings appear everywhere in software:
Usernames Passwords URLs Emails File names Search queries Programming code Documents DNA sequences Messages
That's why string algorithms are extremely important.
37. Most Important Concepts to Remember
STRING │ ┌────────────┴────────────┐ ↓ ↓ Characters Indexing │ │ 'A' 'B' 'C' 0 1 2 3 ↓ s[index]
Important operations:
Length → s.length() Access → s[i] Front → s.front() Back → s.back() Add character → push_back() Remove last → pop_back() Substring → substr() Search → find() Reverse → reverse() Compare → ==, <, >
And the most important DSA techniques to start recognizing are:
Traversal Two pointers Frequency counting Searching String comparison Palindrome checking
Final Summary
Think of a string as:
string s = "HELLO";
which can be viewed as:
0 1 2 3 4 ↓ ↓ ↓ ↓ ↓ ┌────┬────┬────┬────┬────┐ │ H │ E │ L │ L │ O │ └────┴────┴────┴────┴────┘
The key idea is:
A string is a sequence of characters, and many array techniques can be applied to it.
Once you understand indexing, traversal, modification, searching, substring, reversing, palindrome, and character frequency, you have the foundation for string-based DSA problems.