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) \$