Sorting | 450 DSA | Love Babbar
Post
Cancel

# Sorting | 450 DSA | Love Babbar

### Day 1

#### Problem 1: Reverse a string

• Write a function that reverses a string. The input string is given as an array of characters s.
• Leetcode
##### Worst/ Better
• Loop through the string from the back and store the elements in a new string.
• Time Complexity : O(n)
• Space Complexity : O(n)
##### Optimal
• Make two pointers pointing towards the extreme ends and swap till the front < rear.
• Time Complexity : O(n)
• Space Complexity : 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

##### 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)
• Space Complexity : 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 in a string

• Print all the duplicates in the input string.
##### Worst/Better/Optimal
• Either create a hash-array or a hash-map.
• Time Complexity : O(n)
• Space Complexity : O(k) size of the map