3
\$\begingroup\$

Given a string s consisting of lowercase Latin Letters, find the first non repeating character in s.

Input:

The first line contains T denoting the number of testcases. Then follows description of testcases. Each case begins with a single integer N denoting the length of string. The next line contains the string s.

Output:

For each testcase, print the first non repeating character present in string. Print -1 if there is no non repeating character.

Constraints:

1<=T<=50  
1<=N<=100

Example:

Input :

3 
5  
 hello 
12 
zxvczbtxyzvy 
6 
xxyyzz

Output :

h  
c
-1

My approach:

/*package whatever //do not write package name here */

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.util.*;

class GFG {
    private static int firstNonRepNum (String str, int size)
        {
            Hashtable <Character, Integer> count = new Hashtable<>();
            int occurs;

            for (char ch: str.toCharArray())
                {
                    if (!count.containsKey(ch))
                        {
                            count.put(ch,1);
                        }
                    else
                        {
                            occurs = count.get(ch);
                            count.put(ch, occurs+1);
                        }
                }

           for (char ch: str.toCharArray())
            {
                int val = count.get(ch);

                if (val == 1)
                    {
                        return ch;
                    } 
            }                

        return -1;
        }

    public static void main (String[] args) throws IOException{
        //code
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //String line = br.readLine();
        Scanner sc = new Scanner(System.in);

        int numTests = sc.nextInt();

        String line2;
        int size;
        String str;

        for (int i = 0; i < numTests; i++)
            {

                size = sc.nextInt();
                str = sc.next();
                if (firstNonRepNum(str,size) == -1)
                    {
                        System.out.println("-1");
                    }
                else
                    {
                        System.out.println((char)firstNonRepNum(str, size));
                    }   

            }
    }
}

I have the following questions with regards to the above code:

  1. How can I further improve my approach?

  2. Is there a better way to solve this question?

  3. Are there any grave code violations that I have committed?

  4. Can space and time complexity be further improved?

Reference

\$\endgroup\$
1
\$\begingroup\$

Another note:

Your code could be considerably more concise by using the modern .stream():

public static char getFirstUniqueChar(String value) {
    LinkedHashMap<Character, Integer> data = new LinkedHashMap<>();
    for (char c : value.toCharArray()) {
        data.compute(c, (t, u) -> (u == null) ? 1 : ++u);
    }
      var temp = data.entrySet()
              .stream()
              .filter(x -> x.getValue() == 1)
              .findFirst();
    if (temp.isPresent()) {
        return temp.get().getKey();
    }
    return '\0';
}

Instead of returning a -1 this function will return a null character, which can just as easily be trapped.

Notice also the use of .compute which creates a new Entry or adds to an existing one, all in one line.

\$\endgroup\$
  • \$\begingroup\$ Thanks for suggesting a different way using streams. I am pretty weak with it and I hope that I would try solving questions using streams. \$\endgroup\$ – Anirudh Thatipelli Jul 5 '18 at 15:58
4
\$\begingroup\$

Your algorithm is correct. There is no way to reduce time or space complexity, so I will give some less important suggestions.

  1. because you know that there will only be latin letters, we can use an array instead of a hashtable and avoid the overhead. You can decide for yourself if this approach is explicit enough.

    int[] counts = new int[26];
    counts[ch - 'a'] += 1
    
  2. firstNonRepNum() has an argument size, that it does not use.

  3. Your indentation, while mostly consistent, is very odd. It ends up with 8 chars of indent each level. Read some style guides for other ways of indenting. In java most people indent like this.

    public void func(int[] arg) {
        for (int i; arg) {
            if (i % 2) {
                even();
            } else {
                odd();
            }
        }
    }
    
  4. if a variable is only used in a certain scope, declare it in that scope. This helps people who are reading your code because they dont have to search for what count does.

    {
        int occurs = count.get(ch);
        count.put(ch, occurs+1);
    }
    
  5. You call firstNonRepNum() twice. Once to check if there is a solution and once to get the result. Call it once and put the result in a variable.

  6. Remove any unused variable declarations (i.e. String line2) or commented out code as soon as you are sure you don't need it.

\$\endgroup\$
  • \$\begingroup\$ Even if the problem statement clearly states lowercase latin letters only, I would strongly advise against using a character array. This totally invalidates the whole program when asked to extend the problem space to unicode, which the original version does not. (And extending to unicode is to be expected at the same moment where you leave the lab. ;-)) \$\endgroup\$ – mtj Jul 5 '18 at 5:44
  • \$\begingroup\$ Thanks, @Peter for the suggestions. I will keep this in mind from now onwards. \$\endgroup\$ – Anirudh Thatipelli Jul 5 '18 at 15:57
  • \$\begingroup\$ Beginner question: For freshers, is it imperative to follow style guides? It sounds too fastidious. \$\endgroup\$ – Anirudh Thatipelli Jul 5 '18 at 15:57
  • \$\begingroup\$ It isn't necessary to follow style guides to the letter, but it is important to be mindful of the style and readability of your code. Consistancy of naming, indentation, etc is more important. \$\endgroup\$ – Peter Jul 5 '18 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.