{"id":1197,"date":"2020-06-10T14:58:10","date_gmt":"2020-06-10T14:58:10","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1197"},"modified":"2022-03-23T22:46:35","modified_gmt":"2022-03-23T22:46:35","slug":"first-character","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/first-character\/","title":{"rendered":"First character"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

String, Hashing<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

Find the first non-repeating character in the string, print -1 if all characters are repeating.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case<\/h4>\n
Input:\n2\nprepbytesreport\nmettme\n\nOutput:\n4\n-1\n\nExplanation:\nCase-1:\n'p' repeats at index 3 and 11.\n'r' repeats at index 9 and 13.\n'e' repeats at index 7 and 10.\n'p' has already been scanned, which means it has occurred before.\n'b' does not appear after the current position, hence this is the first non-repeating character of the string. So the current index i.e. 4 is our answer.\n\nCase-2:\n'm' repeats at index 4.\n'e' repeats at index 5.\n't' repeats at index 3.\n't' has already been scanned, which means it has occurred before.\n'm' has already been scanned, which means it has occurred before.\n'e' has already been scanned, which means it has occurred before.\nAs we scanned our complete string but no non-repeating character was found so we print -1 as our answer.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach:<\/h4>\n
\n
1) As we have to find the first non-repeating character, so we will scan the whole complete string.
\n2) For every character, we will scan the whole complete string, and see if the current character appears at any index except the current index. If yes, the given character is repeating. If no such value is found, that means this is the first non-repeating character and we print the current index.
\n3) If no such character is found in complete string, that means string contains all repeating character, so we print -1.
\n4) The Above approach scans whole string for every character, which means it take O(N2<\/sup>) time complexity which is inefficient for larger strings. We can decrease time complexity by using a single loop in the following approach.<\/p>\n<\/blockquote>\n
Efficient Approach:<\/h4>\n
\n
1) In this approach, We can find the first non-repeating character if we know the frequency of all characters.<\/p>\n
2) To maintain the frequency of characters, we use hashing technique that uses a hash table.<\/p>\n
    \n
  • Hash Table:<\/em><\/strong> A hash table is an array, where each index represents a Key<\/strong> and value at index represents value<\/strong> associated with the key.<\/li>\n<\/ul>\n
    3) Here character can be converted easily into a valid index, by substracting ASCII value of A<\/code> from it, hence each index starting from 0 to 25 represents characters A<\/code> to Z<\/code> respectively.<\/p>\n
    4) After counting the frequency of all characters in the hash table, we print the index of the first character in string who appears exactly once in the string and have hash value 1.<\/p>\n
    5) If no such character is found we print -1.<\/p>\n<\/blockquote>\n
    Example<\/h3>\n
    \n
      \n
    • \n
      Let’s assume, given string is prepbyters<\/code>, we use a hash table to count the total number of appearances of each character in the given string.<\/p>\n<\/li>\n
    • \n
      We increment the value of hash table by 1<\/code> for the current scanned character, where each index represents a unique character.<\/p>\n<\/li>\n
    • \n
      After scanning whole string our hash table becomes,<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
      \"\"<\/p>\n
      \n
        \n
      • \n
        In the above hash table, every index represents the count of character in the given string, where every index represents a unique character.<\/p>\n<\/li>\n
      • \n
        We again scan string from start, if the current character has a value greater than 1, which means it repeats in the given string. If the value is 1, it only presents at the current index and is non-repeating. As soon as we get such an index, we print the current index as it is the first non-repeating character in the string.<\/p>\n<\/li>\n
      • \n
        If the whole string is scanned, but no such index is found we print -1. <\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
        Solutions<\/h3>\n
        \t\t\t\t\t\t