Optimal Approach Beats Brute Force In String Matching Problem
Brute force approach: O(N^2), SC: O(256). Optimal approach: O(n), SC: O(256). Hash table used to keep count of characters.
Problem
Brute force approach:
TC: O(N^2), SC: O(256) which is constant
Note: This will lead to TLE
class Solution {
public String minWindow(String s, String t) {
int min = Integer.MAX_VALUE;
int start =-1;
int end = -1;
//generating all possible substrings and returning the smallest substring having
//all the character of string t
for(int i =0;i<s.length();i++){
int arr[] = new int[256]; // all the asci characters
//initialize arr with count of character in t
for(int k =0;k<t.length();k++){...