# A readable O(N*log(n)) solution

• The test cases are quite zealous, especially the last one with the alternating "ab" characters, lol. I was reviewing most of the fast solutions, and, to be frank, most of those are not very readable or easy to follow in my opinion. I could not seeing doing one of those in an 1-hour interview question. I could see discussing optimization, but, not coding it in 1-hour. In 1-hour, I would expect, at least, an O(N^2) solution. After, that, I would do follow-up questions on optimization.

At any rate, I think my solution is easy enough to explain without confusion. Maintenance can be a big-deal so something that is readable can go a long way in a team-environment.

However, I still need to give the guys, with the very fast solutions some kudos! Good job guys! Just remember us maintenance folks, please. ;-)

``````public class Solution
{
public IList<int> FindSubstring(string s, string[] words)
{
List<int> indices = new List<int>();

//Only process if we meet criteria
if (!String.IsNullOrEmpty(s) && words.Length > 0 && words[0].Length > 0 &&
s.Length >= words.Length * words[0].Length)
{
int wordLen = words[0].Length;
int totalWordLen = words.Length * words[0].Length;

//Iterate through whole string looking for matches
for (int i = 0; i <= s.Length - totalWordLen; i++)
{
bool isMatched = true;
Dictionary<string,int> wordMap = new Dictionary<string, int>(words.Length);

//Rebuild map for this iteration
for (int k=0; k < words.Length; k++)
{
if (wordMap.ContainsKey(words[k]))//We have a duplicate word
{
wordMap[words[k]]++;
}
else
{
wordMap[words[k]] = 1;
}
}

//Iterate substring to determine if we have a match
for(int j=i; j <= (totalWordLen - wordLen) + i; j += wordLen)
{
string source = s.Substring(j, wordLen);

if (wordMap.ContainsKey(source))
{
if (wordMap[source] == 0)//no more available for match
{
isMatched = false;
break;
}

wordMap[source]--;
}
else
{
isMatched = false;
break;
}
}

if (isMatched)
{
indices.Add(i);
}
}
}

return indices;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.