Home String | 450 DSA | Love Babbar
Post
Cancel

String | 450 DSA | Love Babbar

Problem 1: Reverse a string

Write a function that reverses a string. The input string is given as an array of characters s.

Worst/ Better

Loop through the string from the back and store the elements in a new string.

Time Complexity: $ O(n) $

Auxiliary Space: $ O(n) $

Optimal

Make two pointers pointing towards the extreme ends and swap till the front < rear.

Time Complexity: $ O(n) $

Auxiliary Space: $ O(1) $

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void reverseString(vector<char>& s) {
        char ch;
        for(int i=0, j= s.size() - 1; i<j; i++, j--){
            ch = s[j];
            s[j] = s[i];
            s[i] = ch;
        }
    }
};

Problem 2: Check for palindrome

Given a string S, check if it is palindrome or not.

Worst/ Better/Optimal

Make two pointers pointing towards the extreme ends and check if ch[front] == ch[rear] till the front < rear.

Time Complexity: $ O(n) $

Auxiliary Space: $ O(1) $

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void reverseString(vector<char>& s) {
        char ch;
        for(int i=0, j= s.size() - 1; i<j; i++, j--){
            ch = s[j];
            s[j] = s[i];
            s[i] = ch;
        }
    }
};

Problem 3: Print duplicates

Print all the duplicates in the input string.

Worst/Better/Optimal

Either create a hash-array or a hash-map.

Time Complexity: $ O(n) $

Auxiliary Space: $ O(k) $ (number of distinct characters)

Problem 4: Subjective

Why String is Immutable or Final in Java

Problem 5: To check if strings are rotations of each other or not

Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1? Given s1 = ABCD and s2 = CDAB, return true, given s1 = ABCD, and s2 = ACBD , return false.

Using substr

1
2
3
4
5
6
bool solve(string s1,string s2){
    int n = s1.size(), m = s2.size();
    if(n != m) return false; 
    s1 += s1;
    return (s1.find(s2) != string::npos);
}

Time Complexity: $ O(m*n) $

Auxiliary Space: $ O(1) $

Using queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool solve(string s1, string s2)
{
    int n = s1.size(), m = s2.size();
    if(n != m) return false; 

    queue<char> q1;
    for (int i = 0; i < n; i++)
        q1.push(s[i]);

    queue<char> q2;
    for (int i = 0; i < m; i++)
        q2.push(s2[i]);

    while (m--) {
        char ch = q2.front();
        q2.pop();
        q2.push(ch);
        if (q2 == q1)
            return true;
    }
    return false;
}

Time Complexity: $ O(m*n) $

Auxiliary Space: $ O(m+n) $

This post is licensed under CC BY 4.0 by the author.

Sorting | 450 DSA | Love Babbar

30 Days of Code | Hackerrank