Home 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

Problem 4: Subjective

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

Matrix | 450 DSA | Love Babbar

String | 450 DSA | Love Babbar