Strings, DSA in C++

C++ mein string characters ka sequence hota hai jo double quotes mein enclosed hoti hai. Hum C-style strings (char array) ya phir STL(Standard Template Library) string class ka use karte hain. C++ mein STL ka use easy aur powerful hota hai.

string str = "Hello Beyond Man";

1. String Declaration & Operations

C-style String (char array):

char name[20] = "AR Khan";

C++ STL String:

#include <string>
string name = "AR Khan";

Common Operations:

• Concatenation: str1 + str2
• Access: str[i]
• Assignment: str = "new"

2. In-built String Functions

C++ string class mein bohot saare built-in functions hote hain jo kaam ko easy bana dete hain:

1. length() / size(): string ki length batata hai
2. substr(pos, len) : substring return karta hai
3. compare(s2) : 0 return karta hai agar strings equal ho
4. find(char/str) : index return karta hai agar found
5. push_back(char) : char add karta hai end mein
6. pop_back() : last character remove karta hai

Note: Agar aapko Strings details mein padhni hai aur string ke har ek function ko practical karke samjhna hai to aap is article ko refer kar sakte hai. Strings in Depth

3. Palindrome Check

Ek string di gayi hai, humein check karna hai ki kya woh palindrome hai ya nahi.

Palindrome ka matlab: String ko aage se ya peeche se padhne par same honi chahiye (e.g., "madam", "racecar")

Examples:

1. "madam" → Palindrome (YES)
2. "hello" → Not Palindrome (NO)
3. "12321" → Palindrome (YES)

Approach

Method 1: Brute Force (Naive)

1. Ek nayi string banake original string ko reverse karo
2. Original aur reversed string ko compare karo
3. Agar same hai toh palindrome hai

Problem: Extra space leti hai (O(n))

Method 2: Two Pointer Technique (Optimized)

1. Two pointers use karo - left  (start se) aur right (end se)
2. Har step mein compare karo:

• Agar left aur right characters same hain, toh pointers move karo
• Agar different hain, immediately return "Not Palindrome"

1. Jab tak left < right , repeat karo

Advantage: No extra space (O(1) space complexity)

Dry Run (Step-by-Step Execution)

String: "racecar"

Length: 7

Initialize: left = 0, right = 6

1. Step 1:

• left=0 ('r'), right=6 ('r')
• Same → left++ (1), right-- (5)

2. Step 2:

• left=1 ('a'), right=5 ('a')
• Same → left++ (2), right-- (4)

3. Step 3:

• left=2 ('c'), right=4 ('c')
• Same → left++ (3), right-- (3)

Loop ends (left >= right) → Palindrome

Code

#include <iostream>
#include <string>
using namespace std;

bool isPalindrome(string s) {
    int left = 0;
    int right = s.length() - 1;
    
    while(left < right) {
        if(s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    string input = "racecar";
    if(isPalindrome(input)) {
        cout << "YES, Palindrome!";
    } else {
        cout << "NO, Not Palindrome!";
    }
    return 0;
}

Code Explanation:

1. Initialization:

• left pointer at start (0)
• right pointer at end (length-1)

2. Loop:

• Compare characters at left and right
• If unequal → return false immediately
• Else move pointers towards center

3. Termination:

• If loop completes → all characters matched → return true

Time Complexity Analysis

• Time Complexity: O(n) - Single traversal (n/2 comparisons)
• Space Complexity: O(1) - No extra space used

4. Anagram Check

Question

Humein do strings di gayi hain, humein check karna hai ki kya woh anagram hain ya nahi.

Anagram ka matlab: Dono strings mein same characters same frequency ke saath hone chahiye (bas arrangement alag ho sakta hai).

Examples:

1. "listen" aur "silent" → Anagram (YES)
2. "hello" aur "world" → Not Anagram (NO)
3. "12345" aur "54321" → Anagram (YES)

Approach

Method 1: Sorting (Basic)

1. Dono strings ko sort karo
2. Sorted strings ko compare karo
3. Agar same hai toh anagram hai

Time Complexity: O(nlogn) (sorting ka time)

Method 2: Frequency Counting (Optimized)

1. Ek frequency array/table banayo (26 size ka for alphabets)
2. Pehli string ke har character ki frequency badhao
3. Dusri string ke har character ki frequency ghatao
4. End mein check karo sab frequencies zero hain ya nahi

Time Complexity: O(n) (best approach)

Dry Run (Step-by-Step Execution)

Strings: "listen" aur "silent"

Length: 6 (dono ke liye same)

1. Frequency Table Initialize: All zeros [a-z] → 26 slots

2. Process "listen":

• l → freq['l'-'a']++ (11th index) → 1
• i → freq['i'-'a']++ (8th index) → 1
• s → freq['s'-'a']++ (18th index) → 1
• t → freq['t'-'a']++ (19th index) → 1
• e → freq['e'-'a']++ (4th index) → 1
• n → freq['n'-'a']++ (13th index) → 1

3. Process "silent":

• s → freq['s'-'a']-- (18th index) → 0
• i → freq['i'-'a']-- (8th index) → 0
• l → freq['l'-'a']-- (11th index) → 0
• e → freq['e'-'a']-- (4th index) → 0
• n → freq['n'-'a']-- (13th index) → 0
• t → freq['t'-'a']-- (19th index) → 0

4. Check Frequencies: Sab zero hai → Anagram

Code

#include <iostream>
#include <string>
#include <algorithm> // for sort()
using namespace std;

bool isAnagram(string s1, string s2) {
    // Length check pehle
    if(s1.length() != s2.length()) return false;
    
    // Method 1: Sorting
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());
    return s1 == s2;
    
    /* Method 2: Frequency Counting (Better)
    int freq[26] = {0};
    
    // Increment for s1
    for(char c : s1) freq[tolower(c)-'a']++;
    
    // Decrement for s2
    for(char c : s2) freq[tolower(c)-'a']--;
    
    // Check all zeros
    for(int i=0; i<26; i++)
        if(freq[i] != 0) return false;
    
    return true;
    */
}

int main() {
    string str1 = "listen";
    string str2 = "silent";
    
    if(isAnagram(str1, str2)) {
        cout << "YES, Anagram!";
    } else {
        cout << "NO, Not Anagram!";
    }
    return 0;
}

Code Explanation:

1. Length Check: Agar lengths different hain, directly false return karo
2. Sorting Method:

• Dono strings ko sort karo
• Compare karo sorted versions

1. Frequency Method (Commented):

• 26 size ka array (a-z)
• Pehli string ke liye increment
• Dusri string ke liye decrement
• End mein check sab zero hain ya nahi

Time Complexity Analysis

• Sorting Method: O(nlogn) (sorting ka time)
• Frequency Method: O(n) (best approach)

5. Count Vowels and Consonants

Question

Hame ek string di gayi hai, humein count karna hai:

1. Kitne vowels hain (a, e, i, o, u)
2. Kitne consonants hain (baaki saare alphabets)

Examples:

1. "Hello" → Vowels: 2, Consonants: 3
2. "Python" → Vowels: 1, Consonants: 5
3. "AEIOU" → Vowels: 5, Consonants: 0

Approach

Method 1: Basic Check

1. String ke har character par loop chalao
2. Check karo:

• Agar character vowel hai → vowel count badhao
• Else if character alphabet hai → consonant count badhao

Method 2: Using Set (Optimized for Vowels)

1. Ek set banaye vowels ka {'a','e','i','o','u'}
2. Har character ke liye check karo:

• Agar set mein hai → vowel
• Else if alphabet hai → consonant

Dry Run (Step-by-Step Execution)

String: "Hello World"

Convert to Lowercase: "hello world"

1. Initialization: vowels = 0, consonants = 0
2. Character Checks:

• 'h' → consonant (1)
• 'e' → vowel (1)
• 'l' → consonant (2)
• 'l' → consonant (3)
• 'o' → vowel (2)
• ' ' → skip (space)
• 'w' → consonant (4)
• 'o' → vowel (3)
• 'r' → consonant (5)
• 'l' → consonant (6)
• 'd' → consonant (7)

1. Final Count: Vowels: 3, Consonants: 7

Code with Detailed Explanation

#include <iostream>
#include <cctype> // for tolower()
using namespace std;

void countLetters(string str) {
    int vowels = 0, consonants = 0;
    
    for(char c : str) {
        c = tolower(c); // Handle uppercase
        
        if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
            vowels++;
        }
        else if(c >= 'a' && c <= 'z') { // Only alphabets
            consonants++;
        }
        // Ignore spaces, numbers, special chars
    }
    
    cout << "Vowels: " << vowels << endl;
    cout << "Consonants: " << consonants << endl;
}

int main() {
    string input = "Hello World";
    countLetters(input);
    return 0;
}

Output:

Vowels: 3

Consonants: 7

Code Explanation:

1. Initialization: vowels aur consonants counters
2. Loop Through String:

• Har character ko lowercase mein convert karo
• Vowel check (a,e,i,o,u)
• Else alphabet check (a-z)

Output: Vowel aur consonant counts print karo

Time Complexity Analysis

• Time Complexity: O(n) - Single string traversal
• Space Complexity: O(1) - Constant space used

Longest Substring Without Repeating Characters

Hume ek string di gayi hai, us string mein sabse lambi substring find karni hai jisme koi bhi character repeat na ho.

Examples:

1. "abcabcbb" → "abc" (Length: 3)
2. "bbbbb" → "b" (Length: 1)
3. "pwwkew" → "wke" (Length: 3)

Approach:

1. Har possible substring check karenge
2. Check karenge ki usme koi repeating character hai ya nahi
3. Sabse lambi valid substring ki length ka track rakhenge

Dry Run (Step-by-Step)

String: "abcabcbb"

1. Substring starting at index 0:

• "a" → valid (length 1)
• "ab" → valid (2)
• "abc" → valid (3)
• "abca" → invalid ('a' repeat)

2. Max so far: 3

3. Substring starting at index 1:

• "b" → valid (1)
• "bc" → valid (2)
• "bca" → valid (3)
• "bcab" → invalid ('b' repeat)

4. Max so far: 3

5. Substring starting at index 2:

• "c" → valid (1)
• "ca" → valid (2)
• "cab" → valid (3)
• "cabc" → invalid ('c' repeat)

6. Max so far: 3

7. Continue this for all positions...

Final maximum length: 3

Code

#include <iostream>
#include <string>
using namespace std;

bool allUnique(string s, int start, int end) {
    // Check if all characters in substring are unique
    for(int i = start; i < end; i++) {
        for(int j = i+1; j <= end; j++) {
            if(s[i] == s[j]) {
                return false;
            }
        }
    }
    return true;
}

int lengthOfLongestSubstring(string s) {
    int n = s.length();
    int max_len = 0;
    
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            if(allUnique(s, i, j)) {
                max_len = max(max_len, j-i+1);
            }
            else {
                break; // Further substrings will also be invalid
            }
        }
    }
    
    return max_len;
}

int main() {
    string input = "abcabcbb";
    cout << "Length of longest substring: " 
         << lengthOfLongestSubstring(input);
    return 0;
}

Code Explanation:

1. allUnique() Function:

• Checks if all characters between start and end are unique
• Uses nested loops to compare all pairs

2. Main Function:

• Outer loop: Har starting position ke liye
• Inner loop: Har ending position ke liye
• Checks uniqueness for each substring
• Updates maximum length found

3. Optimization:

• Agar substring invalid mila, toh aage ke substrings bhi invalid honge (break statement)

Time Complexity Analysis

• Time Complexity: O(n³) - Bahut slow for large strings
• Outer loop: O(n)
• Inner loop: O(n)
• allUnique check: O(n)
• Space Complexity: O(1) - Extra space nahi use kiya

Practice Questions

• Check whether a string is a pangram.
• Remove all duplicates from a string.
• Count frequency of each word in a sentence.
• Reverse only vowels in a string.
• Find first non-repeating character.