• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Given a string, find the first character which is non-repetitive

April 13, 2014 by Dhaval Dave

Given a string, find the first character which is non -repetitive i.e that character must not be present anywhere else in the string.

With two different solutions.

Eg : Input : teeterson      
     Output : r, as it is the first element which 
                        is non repetitive.

Solution 1 :

1) Scan the string from left to right and construct the count array.
2) Again, scan the string from left to right and check for count of 
each character, if you find an element who's count is 1, return it.

Time Complexity : O(2N)= O(N)
Space Complexity : O(N)

Solution 2 :

To reduce Time for searching , we can use Hashmap.
Benefit from previous solution:
to get count for 2,3 etc we can easily use this function with little modification
To search for count 1, no need to iterate array again.

map < int , character > m;
map < int , character > : iterator it;
void *getNonRepChar(char *str)
{
    int *count = (int *)calloc(sizeof(int), NO_OF_CHARS);
    int i;
    for (i = 0; *(str+i);  i++){
       count[*(str+i)]++;
       m.insert(make_pair(count,*(str+i)));
    }//for ended
  return count;
}//function ended

 it.find(1);
 if(it != end() ){
   // element found
   character op = it->second ; 
   printd (" %c has count %d" ,op,1); 
  }
 else  
 printf ("Not found Such element");

Time Complexity : O(N)
Space Complexity : O(N)

-IF YOU LIKE OUR EFFORT, PLEASE LIKE AND SHARE OUR FB-PAGE AND SITE

Similar Articles

Filed Under: Hacker Earth Questions, Interview Questions, problem Tagged With: string

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Microsoft BING Interview Experience

FizzBuzz Solution C C++

Binary Tree Isomorphic to each other

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

VMWare Openings

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

SAP Hiring Off-Campus General Aptitude

Possible sizes of bus to carry n groups of friends

Find the kth number with prime factors 3, 5 and 7

Serialise Deserialise N-ary Tree

Client Server C program

Walmart Labs Interview Experience

Fibonacci Hashing & Fastest Hashtable

Handle duplicates in Binary Search Tree

25 horses 5 tracks Find 3 fastest puzzle

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Find the smallest window in a string containing all characters of another string

C++ OOPs Part2

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

Find if two rectangles overlap

Apriori algorithm C Code Data Mining

Count number of ways to reach a given score in a game

Difference between a LinkedList and a Binary Search Tree BST

Binary Tree in Java

Reliance Jio Software Developer Interview Experience

Find if a binary tree is height balanced ?

Maximum occurred Smallest integer in n ranges

Longest Increasing Subsequence

Sort an array according to the order defined by another array

Subset Sum Problem Dynamic programming

Copyright © 2025 · Genesis Framework · WordPress · Log in