IQ 22: Find the first non repeating character in a string



hey guys welcome back I have another coding interview question for you so we're going to do today is write a function that finds the first non repeating character in a string alright so imagine that we have this string here as you can see in this string we have we have the string called content and we set it equal to this string that we have here a a b c c d e and what we want to do is find the first non repeating character within this string and as you can see here the first no repeating character is b so we're going to jump right into it okay so we're going to start off with this string here first of all we have to find the way that we're going to break this string up all right so the best way to do this is to just turn each one of the characters in this string into an array we can do this like this stream content array you want to create an array of this set equal to content dot split okay and we want to split this by an empty string as you can see each one of these letters are separated by an empty string that's why we're splitting them okay so the next thing that we need to do is to create some variables okay so we know we're going to want a variable that holds the count of each one of the characters within this string content so we want int count equal to zero that's what we want to start it off as the count is zero so another thing that we're going to need is this thing called a hash map hash map all right now this hash map is actually going to take in a string as well as an integer all right I'm going to create a new instance of this hash map alright and all right the next thing that we want to do is actually create ourselves well let me explain why we're creating the hash right now we're creating a hash map because a hash map is used to implement an associative array and it contains key value pairs so what we're going to try to do is associate each one of the characters within this string with a specific value so each character in the string is going to be associated with a count of how many times a specific character occurs within this drink all right so now we want to create ourselves a loop alright so for int I equals 0 I is lesser than cont int array dot less so you want to iterate through that array that we created earlier I plus plus okay now in here what we want to do is check in see well as we're iterating through this array list we want to check and see if the hash map of a particular character is empty so we want to go if hm dot get now hm that contains key and then the contains key is going to be the the current you know we're actually before we even do this we have to still we have to create this thing we have to create a variable before we even do this we have to create a variable and we're going to name this variable current letter string current letter all right so you want to set the current letter equal to Khun tin array at position I all right so this current letter is just going to hold the current position of the array that we're in of this array that we're in this content rating all right so then we're going to add our conditional statement so we want to go if not h m dot contains key current letter do you want to do something so what's going on here is that I'm checking to see if the current letter that is being passed in in this particular iteration is existent within this hashmap and if it's not if it doesn't exist within this hashmap then I want to actually add it to the hashmap so I'm going to go HM dot could and then current letter and then the number one and another thing I want to do is let the count equal to one okay now what i'm doing here I'm just adding this current letter that you can see here and I'm adding a count for the current letter so if the current letter has not been added to that particular hashmap then actually want to add it to the hashmap and i want to increase the count associated with that particular number to one alright so after this I want to do an else so this else is basically stating that if the current letter already exists within the hashmap then what I want to do is actually increment the count by one all right so I'm going to go H m dot put so if it's already within that hashmap then on add this current letter and I want to increase the value you want to create on increase the count by one so I'm actually going to go count equals count plus one and then here we're just going to pass and count all right so after we do this we can simply just print out the hash map to see what we have so far so we're going to go sit out hm save and we're actually going to run this and see what we get alright so as you can see down here this is our hash map that we have a and as you can see a occurs two times which is exactly what we're getting here too and then we have B which occurs once one we have C which occurs two times C it occurs two times then we have D which occurs only once D occurs once and then we have E which also occurs once so we have a hash map that takes in each one of the characters and it's associating each one of those characters with the count of each one of the characters so there's something else that we actually want to do after this because we want to find they actually want to find the first none repeating character all right so we want to create ourselves a loop for we censor this alright so you want to go for it I equals zero and then I is lesser than content array dot length okay and then we want to go I plus plus well let's actually that's a property not a mess it all right after we do this we want to actually create a string now string X and then we want to set this equal to content ray at position I all right so we're just storing the current so we're going to iterate through this array list again and we're searching and we just want to set this equal to a variable after we do that small space okay all right so after we do that what we need to do is add ourselves an if conditional statement so if a if hash map dot get X and if this is equal to one then too much white space here all right so if hm get x equals to 1 then we simply just want to go this out X now this X is going to hold this character the first repeating character that doesn't repeat all right so to explain this right here what we're doing is if the hashmap get x equals 1 so as you know we're going through this content array and it's it's starting at the beginning of the array and it's moving to the next element within the array then the next element in the array so as this array is being progressed through it's going to check to see whether some of the elements are duplicated or not so we're basically saying if hm if we go back down here if HM get X off hm that get X right here 12 B equals 1 then we simply just want to print that out and what we also want to do is just add a break right here because after we get the first non-repeating element we simply just want to break out of the loop and the reason we're breaking out of the loop is because we also have other elements within this hash map that also have a 1 but we want to get the first none repeating so from here we have a equals 2 and then for the first number repeating we're going to have B so we actually want to go up here save run this application and this is what we get B which is the first non repeating element and this string that we have here so if you're good acids on it on an interview you know exactly how to solve this problem if you have any questions leave them in the comments below don't forget to like the video if you've learned something here also subscribe and see you on the next one you

6 Comments

  1. Muthaiah Palaniappan said:

    What will be difference between the solution in the video and the below solution in terms of time complexity?
    for(int i = 0; i < input.length(); i++)
    {
    int count = 0;
    for(int j = i + 1; j < input.length(); j++)
    {
    if(input.charAt(i) == input.charAt(j))
    {
    count++;
    break;
    }
    }

    if(count == 0)
    {
    return input.charAt(i);
    }
    }

    return ' ';

    June 26, 2019
    Reply
  2. tgtffr said:

    Does HashMap guarantees that it keep the sequence in which the objects / strings are added?

    June 26, 2019
    Reply
  3. rahil khan said:

    this only works when a string has consecutive repetetive chars, like – AABCCDEE but not for a string like – AABCABBAD

    June 26, 2019
    Reply
  4. Othmane BENTALEB said:

    You put the count as global for all characters, this works for you cause all occurrences of your string characters are consecutive,

    You should do something similar to this
    if(!hm.containsKey(str)){
    hm.put(str, 1);
    }else{
    hm.put(str, hm.get(str) + 1);
    }

    June 26, 2019
    Reply
  5. chinna raj said:

    i used the same program to find the non repeating word in "malayalam"…….result –> {=1, a=4, l=3, m=5, y=1} .. where to change??

    June 26, 2019
    Reply
  6. lokeshwar M said:

    Shouldn't b LinkedHashmap to preserve the order?

    June 26, 2019
    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *