Array ( [0] => [1] => questions [2] => Basic [3] => Non-repeating-Character ) Strings | Non repeating Character | THE INQUISITIVE






Non repeating Character

LEVEL:Beginner

Description

Given a string K. You have to find the first non repeating character from given string.

Input Format

First line contains the string K.

Output Format

Print the first non repeating character.


Example 1:

Input
maximum
Output
a
Example 2:

Input
knowledge is divine
Output
k
Example 3:

Input
he is my favourite hero
Output
i

oops

Login to see Discussion




Approach

Approach 1: using Brute Force

step-i) initialize a character answer to null
step-ii) initialize i to O
step-iii) assign 0 to count
step-iv) assign i to j
step-v) if i equal to j go to step vii
step-vi) if character at i is equal to character at j of strinng then increment the count
step-vii)increment j by one value
step-viii) repeat steps vi and vii till j is less than length of string
step-ix)if count equal to 0 assign character at index i of string to answer and go to step xii
step-x) increment i by one value
step-xi)repeat steps iii to x till i is less than length of string
step-xii) return the count

Time Complexity: O(n^2)
Space Complexity: O(1)

Approach 2: using hashing


step-i) create a char array count of size 256
step-ii) traverse through string increment the value of count array at index equal to ascii value of character of string
step-iii) initialize character answer to null
step-iv) assign 0 to i
step-v) check if the value of count at index equal to ascii of character at i position of string is 1
step-vi) if it is 1 assign that character to answer and go to ix
step-vii) increment i value by one
step-viii) repeat steps v to vii till i is less than length of string
step-ix) return answer

Time Complexity: O(n)
Space Complexity: O(1)


Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

oops

Login to see Solution






     Recommended Questions      

Topic: Strings

Beginner

1. Timing Format2. Date Format3. Palindrome 4. Anagrams5. Balanced Parenthesis6. Equal Strings7. Smallest Window8. Reverse of String9. Distinct Palindromes10. Remove adjacent duplicates11. Run length encoding12. Non repeating Character13. Array of strings14. Find Excel Column15. Transform one string to another16. Move Robot in circular17. Zig Zag concatenation. 18. Min No of elements19. Combination of strings used to dial a number20. Ancient String