Skip to main content

First Unique Character in the String | Interview Question

Introduction:
In this tutorial we are going to solve a very famous interview problem "first unique character in the string".

Problem Statement:
We have a string. and then we have to find very first character present in the string which is unique.
It means we have to return very first character of the string, whose frequency(count) is 1 in the string.
eg: string="hehemon"
     Output: m

Solution:
In this type of problem we prefer hashmap to easily solve the problem. so what we are going to do is, first of all we are going to create a hashmap. and we will store the character as key and index of character as value.
Trick:
whenever the frequency of character is greater than 1. then we will make the value part of that character -1 in the hashmap. it means now this character is not unique. it's frequency is more than 1.

After iterating whole string, we will have a hashmap. In which we have characters and it's index. and if the frequency of character is more than one then we will simply make the index part of that character -1.

Now we will iterate over hashmap, and we will keep a min_index variable to get the minimum index, which is unique. and at the end the value of min_index will be our answer.

Full Code:
Note: we are taking char c for edge cases.

 char firstUniqChar(string &str) {

        char c='0';

        map<char,int>m;

        for(int i=0;i<str.size();i++){

            if(m.find(str[i])!=m.end()){

                auto it=m.find(str[i]);

                it->second=-1;

            }

            else{

                m.insert(make_pair(str[i],i));

            }

        }

        int flag=0;

        int min_index = INT_MAX;

        for(auto it=m.begin();it!=m.end();it++){

            if(it->second!=-1){

                if(it->second<min_index){

                    min_index=it->second;

                    flag=1;

                }

            }

        }

        if(flag)

        return str[min_index];

        else{

            return c;

        }

Conclusion:

whenever you see string problems like this one. and you have no idea that how we can solve this problem. then hashmap is always an option for you. hashmap is easy and efficient. it reduces our time complexity.


Best of luck.




Comments

Post a Comment

Popular posts from this blog

Disjiont Set Union-Find Data Structure | Code In C++

 Introduction:  In this tutorial we are going to write full program of disjoint set union find advance data structure in c++.  Problem Description: Disjoint Set Union (DSU) is an advance data structure, which basically uses in graph algorithms to find cycles. Codes:  Method1: Brute Force #include<bits/stdc++.h> using namespace std; int find(int f,vector<int>&dsuf){     if(dsuf[f]==-1)         return f;     return find(dsuf[f],dsuf); } void union_op(int from, int to, vector<int>& dsuf){     dsuf[from]=to; } bool isCycle(vector<pair<int,int> >&edge_list, vector<int>&dsuf){     for(int i=0;i<edge_list.size();i++){         int parent1=find(edge_list[i].first,dsuf);         int parent2=find(edge_list[i].second,dsuf);         if(parent1==pare...
Post a Comment
Read more

Target Sum | Backtracking Problem

Introduction: In this tutorial we are going to solve a problem "Target Sum" which is from leetcode. and believe me it's really a good problem to understand Backtracking(Recursion). and if you try to understand the problem as well as code you will get a clear picture of Backtracking. Problem Statement: Link To Problem You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and - . For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3. Solution: As given in question, we have two operation + and -. so we will make recursive call for + and - . and if we have sum as target and we have reached upto the last ind...
Post a Comment
Read more

Symmetric Tree | Interview Problem

Introduction: In this tutorial we are going to solve a good question which will clear your doubts on how BFS or level order traversal is useful to solve binary tree problems. this is basically a question from Leetcode, and it is really very good problem to practice BFS. Problem Statement: Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric: But the following [1,2,2,null,3,null,3] is not: Link : Leetcode Link please make binary tree on paper by the given array above. and you will get a clear picture of the problem. what we are going to do in this problem. Solution: As we know we are going to apply BFS to solve this problem. actually you have to just get one thing to solve this problem. we will perform BFS, but with little change or modification. So first we will store the root->val in a vector or array of the left subtree. and during this we will first insert left child and then ...
Post a Comment
Read more