Substring With Concatenation Of All Words

                                            
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return result;
        }
        
        int wordLength = words[0].length();
        int totalLength = wordLength * words.length;
        
        Map<String, Integer> wordCount = new HashMap<>();
        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }
        
        for (int i = 0; i <= s.length() - totalLength; i++) {
            String sub = s.substring(i, i + totalLength);
            if (isConcatenation(sub, wordCount, wordLength)) {
                result.add(i);
            }
        }
        
        return result;
    }
    
    private boolean isConcatenation(String s, Map<String, Integer> wordCount, int wordLength) {
        Map<String, Integer> seen = new HashMap<>();
        for (int j = 0; j < s.length(); j += wordLength) {
            String word = s.substring(j, j + wordLength);
            seen.put(word, seen.getOrDefault(word, 0) + 1);
        }
        return wordCount.equals(seen);
    }
}

                                            
class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if not s or not words:
            return []
        
        word_len = len(words[0])
        words_count = len(words)
        words_len = word_len * words_count
        word_freq = {}
        for word in words:
            if word in word_freq:
                word_freq[word] += 1
            else:
                word_freq[word] = 1
        
        result = []
        for i in range(len(s) - words_len + 1):
            seen = {}
            for j in range(words_count):
                word_start = i + j * word_len
                word = s[word_start:word_start + word_len]
                if word in word_freq:
                    if word in seen:
                        seen[word] += 1
                    else:
                        seen[word] = 1
                    if seen[word] > word_freq[word]:
                        break
                else:
                    break
                if j + 1 == words_count:
                    result.append(i)
        
        return result

                                            
public class Solution {
    public IList<int> FindSubstring(string s, string[] words) {
        List<int> result = new List<int>();
        if (string.IsNullOrEmpty(s) || words == null || words.Length == 0) {
            return result;
        }
        
        int wordLen = words[0].Length;
        int wordsCount = words.Length;
        int totalLen = wordLen * wordsCount;
        
        Dictionary<string, int> wordFreq = new Dictionary<string, int>();
        foreach (string word in words) {
            if (wordFreq.ContainsKey(word)) {
                wordFreq[word]++;
            } else {
                wordFreq[word] = 1;
            }
        }
        
        for (int i = 0; i <= s.Length - totalLen; i++) {
            Dictionary<string, int> seen = new Dictionary<string, int>();
            int j = 0;
            while (j < wordsCount) {
                string currWord = s.Substring(i + j * wordLen, wordLen);
                if (wordFreq.ContainsKey(currWord)) {
                    if (seen.ContainsKey(currWord)) {
                        seen[currWord]++;
                    } else {
                        seen[currWord] = 1;
                    }
                    if (seen[currWord] > wordFreq[currWord]) {
                        break;
                    }
                } else {
                    break;
                }
                j++;
            }
            if (j == wordsCount) {
                result.Add(i);
            }
        }
        
        return result;
    }
}

                                            
/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    if (s.length === 0 || words.length === 0) {
        return [];
    }
    
    const wordLength = words[0].length;
    const wordCount = words.length;
    
    const totalWordsLength = wordLength * wordCount;
    const wordFrequency = {};
    
    for (let word of words) {
        if (wordFrequency[word] === undefined) {
            wordFrequency[word] = 0;
        }
        wordFrequency[word]++;
    }
    
    const result = [];
    
    for (let i = 0; i <= s.length - totalWordsLength; i++) {
        const seen = {};
        let j = 0;
        
        while (j < wordCount) {
            const currentWord = s.substr(i + (j * wordLength), wordLength);
            
            if (!(currentWord in wordFrequency)) {
                break;
            }
            
            if (currentWord in seen) {
                seen[currentWord]++;
            } else {
                seen[currentWord] = 1;
            }
            
            if (seen[currentWord] > wordFrequency[currentWord]) {
                break;
            }
            
            j++;
        }
        
        if (j === wordCount) {
            result.push(i);
        }
    }
    
    return result;
};

                                            
/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    if (s.length === 0 || words.length === 0) {
        return [];
    }
    const wordLength = words[0].length;
    const wordCount = words.length;
    const totalWordsLength = wordLength * wordCount;
    const wordFrequency = {};

    for (let word of words) {
        if (wordFrequency[word] === undefined) {
            wordFrequency[word] = 0;
        }
        wordFrequency[word]++;
    }

    const result = [];
    for (let i = 0; i <= s.length - totalWordsLength; i++) {
        const seen = {};
        let j = 0;
        while (j < wordCount) {
            let nextWordIndex = i + j * wordLength;
            let currentWord = s.substring(nextWordIndex, nextWordIndex + wordLength);
            if (wordFrequency[currentWord] === undefined) {
                break;
            }
            if (seen[currentWord] === undefined) {
                seen[currentWord] = 0;
            }
            seen[currentWord]++;
            if (seen[currentWord] > wordFrequency[currentWord]) {
                break;
            }
            if (j + 1 === wordCount) {
                result.push(i);
            }
            j++;
        }
    }
    
    return result;
};

To solve this coding challenge, we need to identify all starting indices in string

s

from which a concatenated substring of

words

begins. The concatenated substring must include every string in

words

exactly once and in any order.

Explanation:

To tackle this problem, we need to employ a sliding window technique combined with hash maps to efficiently check for the required concatenation of substrings.

Steps to Solve:

Input Checks and Early Exit :

First, check if the input string
s

or the list of words
words

is empty. If so, immediately return an empty list as there can be no valid substrings.

Initial Setup :

Calculate the length of an individual word (
word_len

).
Find the total count of words (
words_count

).
Calculate the length of the entire concatenated substring (
concat_len

), which is simply
word_len

multiplied by
words_count

.

Frequency Dictionary for Words :

Build a frequency dictionary
word_freq

that stores how many times each word appears in the list
words

.

Sliding Window :

Iterate through the string
s

from index
0

to
(len(s) - concat_len + 1)

. This ensures that we only consider starting points of substring windows within bounds.
For each starting point, initialize an empty dictionary
seen

to keep track of the words seen in the current window.

Check Words in Window :

For each starting point, check fixed-length segments of the string
s

that match the length of words in
words

.
Update the
seen

dictionary with the counts of each segment.
If a segment isn't part of the words list or if any word appears more times than it should, break out of the loop early.

Validity Check :

If the segment perfectly matches the required frequency of words, record the start index in the result list.

Return the Result :

After we have checked all possible starting points, return the list of starting indices.

Pseudocode:

                                            
# Check if input string or words list is empty
if s is empty or words is empty:
return empty list

# Initialize required variables
word_len = length of the first word in words
words_count = number of words in words
concat_len = word_len * words_count

# Build frequency dictionary for words
word_freq = empty dictionary
for each word in words:
if word is in word_freq:
increment word_freq[word] by 1
else:
set word_freq[word] to 1

result = empty list

# Iterate through each possible starting index in s
for i from 0 to (length of s - concat_len + 1):
seen = empty dictionary
for j from 0 to words_count - 1:
word_start = i + j * word_len
word = substring of s from word_start to word_start + word_len

# Check if word is in word_freq
if word is in word_freq:
if word is in seen:
increment seen[word] by 1
else:
set seen[word] to 1

# If seen word count exceeds expected count in word_freq, break
if seen[word] > word_freq[word]:
break
else:
break

# If we have checked all words and counts match, add start index to result
if j + 1 == words_count:
append i to result

# Return the result list of starting indices
return result

Detailed Steps in Pseudocode:

Start by checking if the input string
s

and
words

list are empty. Return an empty list if true.
Calculate the length of the words and the total expected length of the concatenated substring (
concat_len

).
Build a frequency dictionary to count occurrences of each word in
words

.
Use a for loop to iterate through the string
s

from the start to
(length of s - concat_len + 1)

.
For each starting index
i

, initialize an empty
seen

dictionary.
Use an inner for loop to check fixed-length segments from the current starting index
i

.
Extract the segment and check if it exists in the frequency dictionary.
Update the
seen

dictionary and ensure the word count doesn't exceed what's expected.
If all words match perfectly in the current window, record the starting index.
Finally, return the resultant list of valid starting indices.

By following these detailed steps within the pseudocode, we ensure the solution is efficient, understandable, and accurate.