CareerCup

Another way to solve this could be:
Create a hashmap for the given strings with key as
"FirstLetter Number LastLetter" for example a4t (addict)
and when a query comes we can simply look into this hash map

for each string do the following
1. find string length (L), if it is 30 then
2. check s[0] is M and s[L-1] is K if yes then
3. verify rest of 28 characters are matching

if 1,2,3 steps are true then given string is not unique and return
if any of 1,2,3 is false then go for next string

We can make a trie from the given set of strings, and then look for the given string,

Still think modified KMP will be faster. The only modification needed is just before each "textIndex" changing, check if the last letter where M28K finishes is 'K'.

I was thinking if we can create a Hash function for all strings and then check if any of the hash key matches for M28K. This will have the cost of creating Hash of all strings.

Thoughts?

I was thinking if we can create a Hash function for all strings and then check if any of the hash key matches for M28K. This will have the cost of creating Hash of all strings.

Thoughts?

Very Simple solution since creating Hash will have space complexity.
Iterate the list and XOR each iterative string with the given string M28K. If they are not 0 then it means it is unique.

We can have a trie constructed. An additional bookkeeping of the a[0].count.a[count] at the every leaf will give us the answer. In fact, we might even get the answer before finishing constructing the trie!

I think the best way is compare the string with all the strings. This will be fastest since at the first mismatch there is no need to match rest of the words in string & go for next string.

{class M28KStringFinder:

    def __init__(self,text):
        self.text=text
        self.key_str_dict=dict()
        self.key_frq_dict=dict()
    def getInStr(self):
        return self.text

    def isKeyUniq(self,key):
        if self.key_frq_dict.has_key(key):
            if self.key_frq_dict.get(key)==1:
                print key + " is unique"
                print self.key_str_dict.get(key)
            else:
                print key + " was not found or not unique"
    
    def populateHash(self):
        for string in self.text:
            cur_key = string[0]+str(string.__len__())+string[string.__len__()-1]
            self.key_str_dict[cur_key]=string
            if self.key_frq_dict.has_key(cur_key):
                self.key_frq_dict[cur_key]+=1
            else:
                self.key_frq_dict[cur_key]=1
            
list1=['a2w3e4r5ts','p0o9i8u7y6t5rs','s23edf4frcf3l','s23edf4fssa3l']

m28KStringFinder = M28KStringFinder(list1)
m28KStringFinder.populateHash()
m28KStringFinder.isKeyUniq('p14s')

I'm think:

# turn the 28 chars in the middle of M28K into bits
bits_target
for s in LIST:
  if len(s) == 30 and s[0] == 'M' and s[29] = 'K':
    # turn the 28 chars in the middle into bits
    bits_current
    # do xor for bits_current and bits_target
    # if result is 0, they are identical, return False
    # otherwise, continue with the next s
# after the LIST is exhausted, return True

boolean checkForUniqueStrings(String str){
 boolean[] char_set = new boolean[128]; //if it is ASCII string.
 for(int i=1; i<str.length()-1; i++){
  int val = str.charAt(i);
  if (char_set[val]){
       return false;
 }
 return true;
   
 }
}

//Time complexity is O(n); space complexity O(1).