CareerCup

Here is my answer for this question:

basicalgos.blogspot.com/2012/04/38-find-substr-based-on-map.html

just a variation of find minimum window which contains all characters ofa string

We can create a suffix tree and and only search for those suffices that start from the characters given in the HashMap and then find the minimum.

I think we can build an inverted list with positions from the raw string just with the keys from map, and check weather the inverted list has successive positions or not.

If this methods makes sense to anyone, please let me know.

Here is the best algo which is O(N) time complexity:
http (double dot) //leetcode (dot) com/2010/11/finding-minimum-window-in-s-which (dot) html

O(n) time Complexity

public class findSubstingSyncWithmap {

  /**
   * @param args
   */
  public static void main(String[] args) {
    String s="acbadrbdady";
    Map m = new HashMap();
    boolean done=false;
    m.put('b', 1);
    m.put('a', 1);
    m.put('d', 2);
    int si=0;
    Set<Character> set = new HashSet<Character>();
    set=m.keySet();
    Map<Character,Integer> mcopy = new HashMap<Character,Integer>();
    mcopy.putAll(m);
   for(int i=0;i<s.length();i++){
     if(set.contains(s.charAt(i))){
       if(done==false)
         si=i;
       done=true;
       int k=(int)mcopy.get(s.charAt(i));
       mcopy.put(s.charAt(i), k-1);
     }
     else{
       Iterator<Integer> it = mcopy.values().iterator();
       while(it.hasNext()){
         if(it.next()!=0){
           done=false;
           mcopy.clear();
           mcopy.putAll(m);
           break;
         }
       }
       if(done==true){
         System.out.println("I have got the substring which is "+s.substring(si, i));
       }
     }
   }
  }
}

find all the permutations of the alphabets and then we can use the KMP algorithm to match the string.

Keep a queue of characters which you have found till now in the text which are in the map as well. While queuing, decrease the count in the map, while dequeuing increase the count in the map.

Here is when we queue and dequeue:

Queue Q
foreach character in text
if map[character] > 0
Q.Enqueue[character]; map[character]--;
if (Q.size == requiredLength) return Q.ToString();
else
while(Q.front() != character)
map[Q.Dequeue]++;
Q.Dequeue; Q.Enqueue[character];

I think I can solve it in O(n) with just comparisons:

So let's use an array of integers as indices such that int arrayIndex[hash.size] = 0. Now iterate along the array and start dropping each index where the array[arrayIndex[index]] is stored in the array. When we find a match, decrement the hash value associated with count and increment index.

If at any point the hash count falls below 0 then set arrayIndex[0] = arrayIndex[index]. We do this to in a way, move the pointer up to the current pointer.

If everything in the hash equals zero then we have a POSSIBLE solution, so calculate the difference between arrayIndex[0] and arrayIndex[n] and compare to the minCount and store arrayIndex[0] as left and arrayIndex[n] as right.

If index == n and arrayIndex[index] < str.length() then we bring the far left pointer up to the front, hash what it's pointing at, increment the count in the hash table and repeat the steps... it's almost like circular pointers...

This is to take care of cases like aaretbda where the first iteration would have pointers at [1]. [5], and [6].... but then would take [1] with 'a' and re-hash it then have that pointer point at [7]...

I know this sounds really confusing but let me know if it makes sense to anyone.

Here is the code for the given problem (C# console app):

class Program
{
static void Main(string[] args)
{
Dictionary<char, int> hashMap = new Dictionary<char, int>();
hashMap.Add('b', 1);
hashMap.Add('d', 1);
hashMap.Add('a', 1);

string parentString = "abcrefbada";
string substring = string.Empty;
if (parentString.GetSpecialSubstring(hashMap, out substring))
{
Log.Comment("Found substring is: " + substring);
}
else
{
Log.Comment("Special substring NOT FOUND!");
}
}
}

static class StringExtensions
{
public static bool GetSpecialSubstring(this string parentString, Dictionary<char, int> hashMap, out string specialSubstring)
{
specialSubstring = string.Empty;

#region Error Checking
//// DO ERROR CHECKING HERE...
if (string.IsNullOrEmpty(parentString))
{
Log.Comment("parent substring cannot be Null or empty.");
return false;
}

if (hashMap == null || hashMap.Count == 0)
{
Log.Comment("hashMap cannot be Null or empty.");
return false;
}

if (parentString.Length < hashMap.Count)
{
Log.Comment("parent string cannot be less than no of characters in hashMap.");
return false;
}

int hashMapCharCount = 0;
foreach (char hashMapChar in hashMap.Keys)
{
int charCount = hashMap[hashMapChar];
if (charCount < 0)
{
Log.Comment("Character count on a hashmap cannot be less than 0.");
return false;
}

hashMapCharCount += charCount;
}

if (parentString.Length < hashMapCharCount)
{
Log.Comment("parent string cannot be less than no of characters in hashMap.");
return false;
}
#endregion

//// START PROCESSING HERE.
Dictionary<char, int> localHashMap = new Dictionary<char, int>(hashMap);

int parentStringProcessingCounter = 0;
bool specialSubstringFound = false;
while (!specialSubstringFound && parentStringProcessingCounter <= (parentString.Length - hashMapCharCount))
{
//parentString[parentStringProcessingCounter]
int count = -1;
if (hashMap.TryGetValue(parentString[parentStringProcessingCounter], out count))
{
//Check if substring exists this character onwards.
specialSubstringFound = isSpecialStringFoundAtIterator(parentString, parentStringProcessingCounter, localHashMap, hashMapCharCount, out specialSubstring);
localHashMap = new Dictionary<char, int>(hashMap);
}

parentStringProcessingCounter++;
}

return specialSubstringFound;
}

private static bool isSpecialStringFoundAtIterator(string parentString, int parentIterator, Dictionary<char, int> hashMap, int hashMapCharCount, out string specialSubstring)
{
specialSubstring = string.Empty;
bool isSpecialSubstringFound = true;

if (parentString.Length - parentIterator < hashMapCharCount)
{
return false;
}

int iterator = 0;
for (iterator = parentIterator; iterator < parentIterator + hashMapCharCount; iterator++)
{
char targetChar = parentString[iterator];
int count = -1;
if (hashMap.TryGetValue(targetChar, out count))
{
if (count <= 0)
{
isSpecialSubstringFound = false;
break;
}

hashMap[targetChar] = count - 1;
}
else
{
isSpecialSubstringFound = false;
break;
}
}

if (isSpecialSubstringFound)
{
specialSubstring = parentString.Substring(parentIterator, hashMapCharCount);
}

return isSpecialSubstringFound;
}
}

public static class Log
{
public static void Comment(string message)
{
Console.WriteLine(" - " + message);
}
}

garimaa.blogspot.in/2012/04/program-in-c.html