DSA

Problem Statement Given a string s, find the longest palindromic substring in s. A palindrome is a sequence of characters that reads the same backward as forward. Your task is to return the longest substring of s that is a palindrome. Example Input:s = “babad” Output:”bab” or “aba” (both are valid) Explanation:The string contains multiple palindromic substrings such as “bab”, “aba”, and “a”. The longest one is either “bab” or “aba”. Approach 1. Expand Around Center 2. Dynamic Programming 3. Brute Force Algorithm Expand Around Center Complexity Implementation C #include <stdio.h>#include <string.h>char* longestPalindrome(char* s) { int start = 0, maxLength = 0; int len = strlen(s); for (int i = 0; i < len; i++) { int l = i, r = i; while (l >= 0 && r < len && s[l] == s[r]) { if (r – l + 1 > maxLength) { start = l; maxLength = r – l + 1; } l–; r++; } l = i; r = i + 1; while (l >= 0 && r < len && s[l] == s[r]) { if (r – l + 1 > maxLength) { start = l; maxLength = r – l + 1; } l–; r++; } } s[start + maxLength] = ‘\0’; return s + start;}int main() { char s[] = “babad”; printf(“Longest Palindromic Substring: %s\n”, longestPalindrome(s)); return 0;} C++ #include <iostream>#include <string>using namespace std;string longestPalindrome(string s) { int start = 0, maxLength = 0, n = s.length(); for (int i = 0; i < n; i++) { int l = i, r = i; while (l >= 0 && r < n && s[l] == s[r]) { if (r – l + 1 > maxLength) { start = l; maxLength = r – l + 1; } l–; r++; } l = i, r = i + 1; while (l >= 0 && r < n && s[l] == s[r]) { if (r – l + 1 > maxLength) { start = l; maxLength = r – l + 1; } l–; r++; } } return s.substr(start, maxLength);}int main() { string s = “babad”; cout << “Longest Palindromic Substring: ” << longestPalindrome(s) << endl; return 0;} Java public class LongestPalindromicSubstring { public static String longestPalindrome(String s) { int start = 0, maxLength = 0; for (int i = 0; i < s.length(); i++) { int l = i, r = i; while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { if (r – l + 1 > maxLength) { start = l; maxLength = r – l + 1; } l–; r++; } l = i; r = i + 1; while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { if (r – l + 1 > maxLength) { start = l; maxLength = r – l + 1; } l–; r++; } } return s.substring(start, start + maxLength); } public static void main(String[] args) { String s = “babad”; System.out.println(“Longest Palindromic Substring: ” + longestPalindrome(s)); }} Python def longest_palindrome(s: str) -> str: start, max_length = 0, 0 for i in range(len(s)): l, r = i, i while l >= 0 and r < len(s) and s[l] == s[r]: if r – l + 1 > max_length: start, max_length = l, r – l + 1 l -= 1 r += 1 l, r = i, i + 1 while l >= 0 and r < len(s) and s[l] == s[r]: if r – l + 1 > max_length: start, max_length = l, r – l + 1 l -= 1 r += 1 return s[start:start + max_length]# Example usageprint(“Longest Palindromic Substring:”, longest_palindrome(“babad”)) C# using System;class LongestPalindromicSubstring { public static string LongestPalindrome(string s) { int start = 0, maxLength = 0; for (int i = 0; i < s.Length; i++) { int l = i, r = i; while (l >= 0 && r < s.Length && s[l] == s[r]) { if (r – l + 1 > maxLength) { start = l; maxLength = r – l + 1; } l–; r++; } l = i; r = i + 1; while (l >= 0 && r < s.Length && s[l] == s[r]) { if (r – l + 1 > maxLength) { start = l; maxLength = r – l + 1; } l–; r++; } } return s.Substring(start, maxLength); } static void Main() { string s = “babad”; Console.WriteLine(“Longest Palindromic Substring: ” + LongestPalindrome(s)); }} JavaScript function longestPalindrome(s) { let start = 0, maxLength = 0; for (let i = 0; i < s.length; i++) { let l = i, r = i; while (l >= 0 && r < s.length && s[l] === s[r]) { if (r – l + 1 > maxLength) { start = l; maxLength = r – l + 1; } l–; r++; } l = i; r = i + 1; while (l >= 0 && r < s.length && s[l] === s[r]) { if (r – l + 1 > maxLength) { start = l; maxLength = r – l + 1; } l–; r++; } } return s.substring(start, start + maxLength);}console.log(“Longest Palindromic Substring:”, longestPalindrome(“babad”));

Problem Statement Given a string s, find the length of the longest substring without repeating characters. Constraints Examples Approach The problem can be solved efficiently using the Sliding Window Technique. Here’s how: Algorithm Code Implementations 1. C #include <stdio.h>#include <string.h>int lengthOfLongestSubstring(char *s) { int n = strlen(s); int max_len = 0, start = 0; int map[128] = {0}; for (int end = 0; end < n; end++) { if (map[s[end]] > 0) { start = (map[s[end]] > start) ? map[s[end]] : start; } map[s[end]] = end + 1; max_len = (max_len > end – start + 1) ? max_len : end – start + 1; } return max_len;}int main() { char str[] = “abcabcbb”; printf(“Length of Longest Substring: %d\n”, lengthOfLongestSubstring(str)); return 0;} 2. C++ #include <iostream>#include <unordered_map>using namespace std;int lengthOfLongestSubstring(string s) { unordered_map<char, int> map; int start = 0, max_len = 0; for (int end = 0; end < s.length(); end++) { if (map.find(s[end]) != map.end()) { start = max(map[s[end]] + 1, start); } map[s[end]] = end; max_len = max(max_len, end – start + 1); } return max_len;}int main() { string str = “abcabcbb”; cout << “Length of Longest Substring: ” << lengthOfLongestSubstring(str) << endl; return 0;} 3. Java import java.util.HashMap;public class LongestSubstring { public static int lengthOfLongestSubstring(String s) { HashMap<Character, Integer> map = new HashMap<>(); int start = 0, max_len = 0; for (int end = 0; end < s.length(); end++) { if (map.containsKey(s.charAt(end))) { start = Math.max(map.get(s.charAt(end)) + 1, start); } map.put(s.charAt(end), end); max_len = Math.max(max_len, end – start + 1); } return max_len; } public static void main(String[] args) { String str = “abcabcbb”; System.out.println(“Length of Longest Substring: ” + lengthOfLongestSubstring(str)); }} 4. Python def length_of_longest_substring(s: str) -> int: char_map = {} start, max_len = 0, 0 for end, char in enumerate(s): if char in char_map and char_map[char] >= start: start = char_map[char] + 1 char_map[char] = end max_len = max(max_len, end – start + 1) return max_len# Example usageprint(“Length of Longest Substring:”, length_of_longest_substring(“abcabcbb”)) 5. C# using System;using System.Collections.Generic;class LongestSubstring { public static int LengthOfLongestSubstring(string s) { Dictionary<char, int> map = new Dictionary<char, int>(); int start = 0, max_len = 0; for (int end = 0; end < s.Length; end++) { if (map.ContainsKey(s[end]) && map[s[end]] >= start) { start = map[s[end]] + 1; } map[s[end]] = end; max_len = Math.Max(max_len, end – start + 1); } return max_len; } static void Main(string[] args) { string str = “abcabcbb”; Console.WriteLine(“Length of Longest Substring: ” + LengthOfLongestSubstring(str)); }} 6. JavaScript Copy codefunction lengthOfLongestSubstring(s) { let charMap = new Map(); let start = 0, maxLen = 0; for (let end = 0; end < s.length; end++) { if (charMap.has(s[end]) && charMap.get(s[end]) >= start) { start = charMap.get(s[end]) + 1; } charMap.set(s[end], end); maxLen = Math.max(maxLen, end – start + 1); } return maxLen;}console.log(“Length of Longest Substring:”, lengthOfLongestSubstring(“abcabcbb”)); Time Complexity Space Complexity

The goal is to identify the smallest positive number absent from an unsorted array arr[] including both positive and negative items. Note: You have original array modification power. Examples By Marking Indices – O(n) Time and O(1) Space The concept is to note the presence of elements inside the same array. Since 1 is the smallest positive integer, first we look to see whether 1 is there; should it be absent, the response is 1. All numbers that are either negative or greater than the array size are converted to 1 otherwise to maintain all numbers within a range of 1 to n. We next index the numbers using their values. To indicate the presence of a number x, we are adding n to the number existing at index x – 1. At last, we search the array for the first unmarked index to obtain the smallest missing positive value. C++ C Java Python C# JavaScript Output 3

First, all positive integers should be migrated to the left side of the array. We next traverse over this left segment and negating the value at index (x – 1) marks the occurrences of every number x. Finally, go over the left section once more and, looking for the first unmarked piece, determine the missing number. Alternate Approach] By Marking Indices – O(n) Time and O(1) Space The goal is to identify the smallest positive number absent from an unsorted array arr[] including both positive and negative items. Note: You have original array modification power. Illustrations: By Negating Array Elements – O(n) Time and O(1) Space Should our array consist entirely of positive numbers, we can record the presence of a number x by negating the number at index x – 1 in the array. We can thus find our first missing element by first looking for the first unmarked element in the same array. Moving all the positive integers to the left side of the array will help us to apply this method for an array comprising both positive and negative numbers. After this is finished, we may use the positive array technique on this left side—an array of positive numbers. C++ C Java Python C# JavaScript Output 3

We shall answer the most often requested interview question “Combination Sum II – Find all unique combinations” in this post. Find all unique combinations in candidates where the candidate numbers add to target given a set of candidate numbers (candidates) and a target number. Every number in the candidates could just be used once in the mix. Note: The set of solutions has to be devoid of repeating combinations. Some instances are: Solution: Disclaimer: Don’t jump directly to the solution, try it out yourself first. Solution 1: Using extra space and time complexity  Approach: Defining the Recursive Function: Sort the elements before beginning the recursive call; the ans should not be duplicated and should include the combinations in sorted sequence. We begin with the index 0; at index 0 we have n – 1 ways to choose the first element of our subsequence. See if our ds could benefit from the current index value. If so, include it into the ds and shift the index by one. As shifting the index skip the consecutive repeated elements will create duplicate sequences. After the call make sure to pop the element from the ds. Reduce the target by arr[i] and call the recursive call for f(idx + 1,target – 1,ds,ans).(Seeing the example repeatedly will help you to grasp). If arr[i] > target, then stop the recursive function since there is no need in checking; the index will be moving by 1 all the entries to its right will be in increasing order. Base state: Add the ds to the ans return anyhow the goal value is zero. Recursive call represented for the provided example below: Code C++ Java Python Output: [ [ 1 1 6 ][ 1 2 5 ][ 1 7 ][ 2 6 ] ] Time Complexity:O(2^n*k) Space Complexity:O(k*x)

The concept is like Cycle Sort and moves every element in the array to its proper place depending on its value. Thus, for any number, say x, arrange 1 ≤ x ≤ n at the (x – 1)th index. At last, go over the array looking for whether the numbers match the predicted indexes or not. The first missing positive number results from the first spot where the number does not match its index. The smallest missing positive integer is n + 1, if all the numbers from 1 to n match their proper indices. C++ C Java Python C# JavaScript Output 3

The goal is to identify the smallest positive number absent from an unsorted array arr[] including both positive and negative items. Note: You have original array modification power. Example: Table of Content [Naive approach] By Sorting – O(n*log n) Time and O(n) Space Sorting the array will help one to presume a missing number as 1. Now go over the array iteratively and for every element arr[i], Should arr[i] be a missing number, increase missing number by one.Proceed to hunt for the missing number if arr[i] < missing number.Should arr[i] surpass the missing number, break and provide the missing number back. C++ C Java Python C# JavaScript Output 3

The visited array will help to track which integers from the original array were present. We note the matching place in the visited array for every positive number in the input array. We then search the visited array looking for the first unvisited point. The first unvisited index reveals the initial missing positive number.We are simply noting numbers falling between 1 and n here. C++ C Java Python C# JavaScript Output 3

Problem Statement: Given an array of distinct integers and a target integer, find all unique combinations in the array where the numbers sum to the target. You may use the same number multiple times. The numbers in each combination should be in non-descending order, and the combinations themselves should be unique. Approach: Examples:  Code Implementations: Java: import java.util.ArrayList;import java.util.List;public class CombinationSum { public static List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<>(); backtrack(candidates, target, 0, new ArrayList<>(), result); return result; } private static void backtrack(int[] candidates, int target, int start, List<Integer> combination, List<List<Integer>> result) { if (target == 0) { result.add(new ArrayList<>(combination)); return; } for (int i = start; i < candidates.length; i++) { if (candidates[i] > target) continue; combination.add(candidates[i]); backtrack(candidates, target – candidates[i], i, combination, result); combination.remove(combination.size() – 1); } } public static void main(String[] args) { int[] candidates = {2, 3, 6, 7}; int target = 7; List<List<Integer>> result = combinationSum(candidates, target); System.out.println(result); }} Python: def combination_sum(candidates, target): result = [] def backtrack(remaining, combination, start): if remaining == 0: result.append(list(combination)) return for i in range(start, len(candidates)): if candidates[i] > remaining: continue combination.append(candidates[i]) backtrack(remaining – candidates[i], combination, i) combination.pop() candidates.sort() backtrack(target, [], 0) return result# Example usage:candidates = [2, 3, 6, 7]target = 7print(combination_sum(candidates, target)) C#: using System;using System.Collections.Generic;class CombinationSum { public static IList<IList<int>> CombinationSumMethod(int[] candidates, int target) { IList<IList<int>> result = new List<IList<int>>(); Array.Sort(candidates); Backtrack(candidates, target, 0, new List<int>(), result); return result; } private static void Backtrack(int[] candidates, int target, int start, List<int> combination, IList<IList<int>> result) { if (target == 0) { result.Add(new List<int>(combination)); return; } for (int i = start; i < candidates.Length; i++) { if (candidates[i] > target) continue; combination.Add(candidates[i]); Backtrack(candidates, target – candidates[i], i, combination, result); combination.RemoveAt(combination.Count – 1); } } public static void Main(string[] args) { int[] candidates = { 2, 3, 6, 7 }; int target = 7; var result = CombinationSumMethod(candidates, target); foreach (var combo in result) { Console.WriteLine(string.Join(“, “, combo)); } }} JavaScript: function combinationSum(candidates, target) { const result = []; function backtrack(remaining, combination, start) { if (remaining === 0) { result.push([…combination]); return; } for (let i = start; i < candidates.length; i++) { if (candidates[i] > remaining) continue; combination.push(candidates[i]); backtrack(remaining – candidates[i], combination, i); combination.pop(); } } candidates.sort((a, b) => a – b); backtrack(target, [], 0); return result;}// Example usage:const candidates = [2, 3, 6, 7];const target = 7;console.log(combinationSum(candidates, target)); Example Input and Output: Input: candidates = [2, 3, 6, 7]target = 7 Output: plaintextCopy code[[2, 2, 3], [7]] The provided implementations use backtracking to explore all possible combinations and ensure the results meet the problem’s requirements. You said: write in c,cpp ChatGPT said: ChatGPT C Implementation #include <stdio.h>#include <stdlib.h>void findCombinations(int* candidates, int n, int target, int* combination, int combIndex, int start) { if (target == 0) { // Print the current combination for (int i = 0; i < combIndex; i++) { printf(“%d “, combination[i]); } printf(“\n”); return; } for (int i = start; i < n; i++) { if (candidates[i] > target) continue; combination[combIndex] = candidates[i]; findCombinations(candidates, n, target – candidates[i], combination, combIndex + 1, i); }}void combinationSum(int* candidates, int n, int target) { int* combination = (int*)malloc(target * sizeof(int)); // Allocate memory for combinations findCombinations(candidates, n, target, combination, 0, 0); free(combination); // Free allocated memory}int main() { int candidates[] = {2, 3, 6, 7}; int n = sizeof(candidates) / sizeof(candidates[0]); int target = 7; printf(“Combinations that sum up to %d:\n”, target); combinationSum(candidates, n, target); return 0;} C++ Implementation #include <iostream>#include <vector>#include <algorithm>using namespace std;void findCombinations(vector<int>& candidates, int target, vector<int>& combination, int start, vector<vector<int>>& result) { if (target == 0) { result.push_back(combination); return; } for (int i = start; i < candidates.size(); i++) { if (candidates[i] > target) continue; combination.push_back(candidates[i]); findCombinations(candidates, target – candidates[i], combination, i, result); combination.pop_back(); }}vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> result; vector<int> combination; sort(candidates.begin(), candidates.end()); findCombinations(candidates, target, combination, 0, result); return result;}int main() { vector<int> candidates = {2, 3, 6, 7}; int target = 7; vector<vector<int>> result = combinationSum(candidates, target); cout << “Combinations that sum up to ” << target << “:\n”; for (const auto& comb : result) { for (int num : comb) { cout << num << ” “; } cout << endl; } return 0;}

Problem Statement: Write a program to solve a given 9×9 Sudoku puzzle using a backtracking algorithm. The Sudoku grid contains integers from 1 to 9, with 0 representing empty cells that need to be filled. The solution should satisfy the following conditions: Approach: Example Code Implementations: C: #include <stdio.h>#include <stdbool.h>#define N 9bool isValid(int grid[N][N], int row, int col, int num) { for (int x = 0; x < N; x++) { if (grid[row][x] == num || grid[x][col] == num || grid[row – row % 3 + x / 3][col – col % 3 + x % 3] == num) { return false; } } return true;}bool solveSudoku(int grid[N][N]) { int row, col; bool emptyCell = false; for (row = 0; row < N; row++) { for (col = 0; col < N; col++) { if (grid[row][col] == 0) { emptyCell = true; break; } } if (emptyCell) break; } if (!emptyCell) return true; for (int num = 1; num <= 9; num++) { if (isValid(grid, row, col, num)) { grid[row][col] = num; if (solveSudoku(grid)) return true; grid[row][col] = 0; } } return false;}void printGrid(int grid[N][N]) { for (int r = 0; r < N; r++) { for (int d = 0; d < N; d++) { printf(“%d “, grid[r][d]); } printf(“\n”); }}int main() { int grid[N][N] = { {5, 3, 0, 0, 7, 0, 0, 0, 0}, {6, 0, 0, 1, 9, 5, 0, 0, 0}, {0, 9, 8, 0, 0, 0, 0, 6, 0}, {8, 0, 0, 0, 6, 0, 0, 0, 3}, {4, 0, 0, 8, 0, 3, 0, 0, 1}, {7, 0, 0, 0, 2, 0, 0, 0, 6}, {0, 6, 0, 0, 0, 0, 2, 8, 0}, {0, 0, 0, 4, 1, 9, 0, 0, 5}, {0, 0, 0, 0, 8, 0, 0, 7, 9} }; if (solveSudoku(grid)) { printGrid(grid); } else { printf(“No solution exists”); } return 0;} C++: #include <iostream>#include <vector>using namespace std;const int N = 9;bool isValid(vector<vector<int>>& grid, int row, int col, int num) { for (int x = 0; x < N; x++) { if (grid[row][x] == num || grid[x][col] == num || grid[row – row % 3 + x / 3][col – col % 3 + x % 3] == num) { return false; } } return true;}bool solveSudoku(vector<vector<int>>& grid) { int row, col; bool emptyCell = false; for (row = 0; row < N; row++) { for (col = 0; col < N; col++) { if (grid[row][col] == 0) { emptyCell = true; break; } } if (emptyCell) break; } if (!emptyCell) return true; for (int num = 1; num <= 9; num++) { if (isValid(grid, row, col, num)) { grid[row][col] = num; if (solveSudoku(grid)) return true; grid[row][col] = 0; } } return false;}void printGrid(vector<vector<int>>& grid) { for (int r = 0; r < N; r++) { for (int d = 0; d < N; d++) { cout << grid[r][d] << ” “; } cout << endl; }}int main() { vector<vector<int>> grid = { {5, 3, 0, 0, 7, 0, 0, 0, 0}, {6, 0, 0, 1, 9, 5, 0, 0, 0}, {0, 9, 8, 0, 0, 0, 0, 6, 0}, {8, 0, 0, 0, 6, 0, 0, 0, 3}, {4, 0, 0, 8, 0, 3, 0, 0, 1}, {7, 0, 0, 0, 2, 0, 0, 0, 6}, {0, 6, 0, 0, 0, 0, 2, 8, 0}, {0, 0, 0, 4, 1, 9, 0, 0, 5}, {0, 0, 0, 0, 8, 0, 0, 7, 9} }; if (solveSudoku(grid)) { printGrid(grid); } else { cout << “No solution exists” << endl; } return 0;} Java: public class SudokuSolver { public static boolean isValid(int[][] board, int row, int col, int num) { for (int x = 0; x < 9; x++) { if (board[row][x] == num || board[x][col] == num || board[row – row % 3 + x / 3][col – col % 3 + x % 3] == num) { return false; } } return true; } public static boolean solveSudoku(int[][] board) { for (int row = 0; row < 9; row++) { for (int col = 0; col < 9; col++) { if (board[row][col] == 0) { for (int num = 1; num <= 9; num++) { if (isValid(board, row, col, num)) { board[row][col] = num; if (solveSudoku(board)) return true; board[row][col] = 0; } } return false; } } } return true; } public static void printBoard(int[][] board) { for (int[] row : board) { for (int num : row) { System.out.print(num + ” “); } System.out.println(); } } public static void main(String[] args) { int[][] board = { {5, 3, 0, 0, 7, 0, 0, 0, 0}, {6, 0, 0, 1, 9, 5, 0, 0, 0}, {0, 9, 8, 0, 0, 0, 0, 6, 0}, {8, 0, 0, 0, 6, 0, 0, 0, 3}, {4, 0, 0, 8, 0, 3, 0, 0, 1}, {7, 0, 0, 0, 2, 0, 0, 0, 6}, {0, 6, 0, 0, 0, 0, 2, 8, 0}, {0, 0, 0, 4, 1, 9, 0, 0, 5}, {0, 0, 0, 0, 8, 0, 0, 7, 9} }; if (solveSudoku(board)) { printBoard(board); } else { System.out.println(“No solution exists”); } }} Python: def is_valid(board, row, col, num): for x in range(9): if board[row][x] == num or board[x][col] == num or \ board[row – row % 3 + x // 3][col – col % 3 + x % 3] == num: return False return Truedef solve_sudoku(board): for row in range(9): for col in range(9): if board[row][col] == 0: for num in range(1, 10): if is_valid(board, row, col, num): board[row][col] = num if solve_sudoku(board): return True board[row][col] = 0 return False return Truedef print_board(board): for row in board: print(” “.join(map(str, row)))if __name__ == “__main__”: board = [ [5, 3, 0, 0, 7, 0, 0, 0, 0], [6, 0, 0, 1, 9, 5, 0, 0, 0], [0, 9, 8, 0, 0, 0, 0, 6, 0], [8, 0, 0, 0, 6, 0, 0, 0, 3], [4, 0, 0, 8, 0, 3, 0, 0, 1], [7, 0, 0, 0, 2, 0, 0,