Problems and solution

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Input: nums = [2,7,11,15], target = 9 Output: [0,1]

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> numMap =  new HashMap<>();

        for(int i = 0 ; i < nums.length;i++ ){
           int complement = target-nums[i];
           if(numMap.containsKey(complement)){
            return new int[]{numMap.get(complement),i};
           }
           numMap.put(nums[i],i);

        }
        return null;

    }
}

Substring with concatenation of All words

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words. Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]

Output: [0,9]

Explanation:

The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words. The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
       List<Integer> ans = new ArrayList<Integer>();
       Map<String,Integer> map = new HashMap<String,Integer>();
       int wordCount = words.length;
       int wordlength = words[0].length();
       for(String word : words){
        map.put(word,map.getOrDefault(word,0)+1);
       }
       for (int i = 0; i<= s.length() - wordlength*wordCount ;i++){
            Map<String,Integer> copymap = new HashMap<String,Integer>(map);
            for(int j = 0; j <wordCount;j++ ){
                String subString = s.substring(i+j*wordlength,i+(j+1)*wordlength);
                if(copymap.containsKey(subString)){
                    int count = copymap.get(subString);
                    if (count == 1){
                        copymap.remove(subString);
                    }else{
                        copymap.put(subString,count-1);
                    }
                    if (copymap.isEmpty()){
                        ans.add(i);
                        break;
                    }
                }
                else{
                    break;
                }
            }
       }
       return ans;
    }
}

Optimised code

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s.length() == 0 || words.length == 0) return result;

        int wordLength = words[0].length();
        int wordCount = words.length;
        int totalLength = wordLength * wordCount;

        Map<String, Integer> wordMap = new HashMap<>();
        for (String word : words) {
            wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i < wordLength; i++) {
            int left = i, right = i;
            Map<String, Integer> windowMap = new HashMap<>();
            int count = 0;

            while (right + wordLength <= s.length()) {
                String word = s.substring(right, right + wordLength);
                right += wordLength;

                if (wordMap.containsKey(word)) {
                    windowMap.put(word, windowMap.getOrDefault(word, 0) + 1);
                    count++;

                    while (windowMap.get(word) > wordMap.get(word)) {
                        String leftWord = s.substring(left, left + wordLength);
                        windowMap.put(leftWord, windowMap.get(leftWord) - 1);
                        count--;
                        left += wordLength;
                    }

                    if (count == wordCount) {
                        result.add(left);
                    }
                } else {
                    windowMap.clear();
                    count = 0;
                    left = right;
                }
            }
        }
        return result;
    }
}