Find the First non repeated character in the String

Find the first nonrepeating character from the string. 

Example 1:

Input : str="Hi Hello World"
Output: i
Approach 1:

Java

public class NonRepeatableFirstChar {
    public static void main(String[] args) {
         //input string must contain one 
         //character which occur ones
        String str = "Hi Hellow World";
        char c = nonRepeatedFirst(str);
        System.out.println("Char is " + c);
    }

    public static char nonRepeatedFirst(String str) {
        char[] c = str.toCharArray();
        char ch = '\0';
        int length = str.length();
        int index = -1;
        while (length >= 0) {
            index++;
            ch = str.charAt(index);
            if (Character.isLetter(ch)) {
                int check = 0;
                for (int i = 0; i < c.length; i++) {
                    if (Character.isLetter(c[i]) && ch == c[i] && index != i) {
                        check = 1;
                        break;
                    }
                }
                if (check == 0)
                    return ch;
            }
            length--;
        }
        return ch;
    }
}

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

C++

#include <bits/stdc++.h>
using namespace std;
char firstNonRepeating(string str)
{
    int n=str.size();
    char ans='#';
    for(int i=0;i<n;i++)
      {
          ans=str[i];
          int j=i+1;
          int flag=0;
          for(j=i+1;j<n;j++)
            {
               if(str[j]==ans)
                  {
                      flag=1;
                      break;
                  }
            }
         if(flag==0)
            return ans;

      }
      return ans;
}
int main()
{
    string str="Hi Hello World";
    char first=firstNonRepeating(str);
    cout<<"First Non repeating is ";
    cout<<first<<"\n";
    return 0;
}
// Time Complexity : O(n^2)
// Space Complexity : O(1)


Approach:2

Java


import java.util.HashSet;

public class NonRepeatableFirstChar1 {
    public static void main(String[] args) {
        // input string must contain one
        // character which occur ones
        String str = "Hi Hellow World";
        char c = nonRepeatedFirst(str);
        System.out.println("Char is " + c);
    }

    // function to find the first
    // non repeating character
    static char nonRepeatedFirst(String str) {
        HashSet<Characterst = new HashSet<>();
        char ans = '\0';
        for (int i = str.length() - 1; i >= 0; i--) {
            if (Character.isLetter(str.charAt(i))) {
                if (!st.contains(str.charAt(i))) {
                    ans = str.charAt(i);
                    st.add(ans);
                }
            }
        }
        return ans;
    }
}
// Time Complexity : O(n)
// Space Complexity : O(n)

C++

#include <bits/stdc++.h>
using namespace std;

//function to find the first 
//non repeating character
char firstNonRepeating(string str)
{
    set<char> st;
    char ans='#';
    for(int i=str.size()-1;i>=0;i--)
      {
          if(str[i]!=' ')
            {
                if(st.find(str[i])==st.end())
                  {
                      ans=str[i];
                      st.insert(str[i]);
                  }
            }
      }
    return ans;
}
int main()
{

    //input string must contain one 
    //character which occur ones
    string str="Hi Hello World";
    char first=firstNonRepeating(str);
    cout<<"First Non Repeating is ";
    cout<<first<<"\n";
    return 0;
}

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


No comments:

Post a Comment