Samar Srivastav

Problem : Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.**bold text

Solution : Time Complexity (O(3^n))

JAVA
1class Solution {
2    public boolean checkValidString(String s) {
3        // Start recursive helper with index 0 and count 0
4        return helper(0, 0, s);
5    }
6
7    public boolean helper(int idx, int count, String s) {
8        // If at any point count becomes negative, it means there are more ')' than '('
9        if (count < 0) return false;
10
11        // If we have processed the entire string, check if all open brackets are closed
12        if (idx == s.length()) {
13            return count == 0;
14        }
15
16        boolean ans = false;
17
18        // If the current character is '(', we increase the open count
19        if (s.charAt(idx) == '(') {
20            ans = helper(idx + 1, count + 1, s);
21        }
22        // If the current character is ')',...

Problem : You are given an array of non-overlapping intervals...

Solution : Time Complexity: O(n)

JAVA
1//in : given intervals
2//nIn : new interval to insert
3public int[][] insert(int[][] in, int[] nIn) {
4    ArrayList<int[]> al = new ArrayList<>();
5    int i = 0;
6    int n = in.length;
7
8    // Step 1: Add intervals before nIn (no overlap)
9    while (i < n && in[i][1] < nIn[0]) {
10        al.add(in[i]);
11        i++;
12    }
13
14    // Step 2: Merge overlapping intervals
15    int l = nIn[0], r = nIn[1];
16    while (i < n && in[i][0] <= nIn[1]) {
17        l = Math.min(l, in[i][0]);
18        r = Math.max(r, in[i][1]);
19        i++;
20    }
21    al.add(new int[]{l, r});
22
23    // Step 3: Add remaining intervals (no overlap)
24    while (i < n) {
25        al.add(in[i]);
26        i++;
27    }
28
29    // Convert list to array
30    return al.toArray(new int[al.size()][2]);
31}

problem link : Longest Substring Without Repeating Characters

Brute Force Solution O(n^3) time complexity

JAVA
1public int lengthOfLongestSubstring(String s) {
2    int len = 0;
3    // Iterate through all possible substrings starting at index i
4    for (int i = 0; i < s.length(); i++) {
5        for (int j = i; j < s.length(); j++) {
6            // Get substring from index i to j
7            String sub = s.substring(i, j + 1);
8            // Use a set to check for duplicate characters
9            HashSet<Character> set = new HashSet<>();
10            int f = 0;
11            // Check if the substring has all unique characters
12            for (int k = 0; k < sub.length(); k++) {
13                if (set.contains(sub.charAt(k))) {
14                    f = 1; // Duplicate found
15                    break;
16                }
17                set.add(sub.charAt(k));
18            }
19            // If all characters a...