Find first non repeating character without using hashmap

Question

I wanted to find first non repeating character in a string. I wrote the following function in which I am stuck at one point. Google tells me the hashmap method for this but I'll be grateful if someone could help me with my code.

public static Character firstNonRepeatedChar(String line) {

        Character c = null;
        int strLength = line.length();

        for (int i =0; i<strLength-1; i++){

            int flag = 0;
            for(int j = i+1; j<strLength-i; j++){

                if(line.charAt(i) == line.charAt(j)){
                    flag++;
                    break;
                }
                else
                    continue;
            }

            if (flag==0){
                c = line.charAt(i);
                break;
            }


        }
        return c;
    }
}

Problem : How can I put a check that the repeating character that is already checked once is not checked again. Ex: If my string is "hhello" then the code first compares the h at index 0 with all the other characters. Since its repeating the next iteration of outer for loop starts in which i now points to index 1 of the string i.e the repeating h and compares it with the rest of elements. Since it does not get a repeating instance it returns 'h' as non repeating character which is wrong.

How can I fix this? Is there any way? Pls help

EDIT: Repeating character need not be the immediate next character. Ex: In string "helloWorld" characters 'l' and 'o' are repeating. In string "hehelo" characters 'h' and 'e' are repeating and first non repeating character will be 'l'

Answer 1

This one is for PHP

<?php

$string = "ABBGAACCE";

$stringArray = str_split($string); // string converted to array
$temp_array = [];
$non_repeating_array = get_first_non_repeating($stringArray, $temp_array);

echo reset($non_repeating_array); // display first non repeating character from string

function get_first_non_repeating($stringArray, $temp_array)
{
    $repeating = []; // store all repeating characters
    foreach($stringArray as $key => $char)
    {
        if(array_key_exists($char, $temp_array)) // check if character was already saved meaning it is repeating
        {
            array_push($repeating, $char); // push all repeating character in a variable
            $stringArray = array_diff($stringArray, $repeating); // subtract repeating characters from the string array
        }else{
            $temp_array[$char] = 1;
        }
    }
    return $stringArray; // returns the non repeating characters
}

Answer 2

Below method will return you what you are looking.

public static char getFirstNonRepeatedChar(String input) {        
    char c = 0;
    for (int i =0; i<input.length(); i++){
        int flag = 0;
        for(int j = 0; j<input.length(); j++){
            if(input.charAt(i) == input.charAt(j)){
                flag++;
            }
            if(flag>1)
                break;
        }
        if (flag == 1){
            c = input.charAt(i);
            break;
        }
    }
    return c;
}

Answer 3

The easiest way to flag doublets would be to replace the characters with a none printable one. You can then skip these positions. But this will add another O(n) to your loop replacing the characters. The worst case would result in O(n^3). Optimizing you could write an inner loop replacing only the characters ahead of your current position. This would result in a O(n^2) again, because currently you have O(n^2) (n*n/2).

UPDATE Added code and fixed a bug, where the non repeating character is at last position of the String. Instead of processing the String, now processing the char[].

private static final char FLAG = '\u0000';

public static Character firstNonRepeatedChar(String line)
{
    final char[] chars = line.toCharArray();
    Character c = null;

    final int strLength = chars.length;

    for (int i = 0; i < strLength; i++)
    {
        if (chars[i] == FLAG)
        {
            continue;
        }

        int flag = 0;
        for (int j = i + 1; j < strLength; j++)
        {
            if (chars[i] == chars[j])
            {
                flag++;
                chars[j] = FLAG;
            }
        }

        if (flag == 0)
        {
            c = chars[i];
            break;
        }
    }
    return c;
}

Answer 4

Hint 1: A repeating character¹ is one that is the same as the previous character in the String. A non-repeating character is .........

Implement that!

Hint 2: You don't need a nested loop.

---

UPDATE

I see. So you are using "non-repeating character" to mean something different to what most people would mean. What you are actually looking for is the first character that appears only once in the entire string.

Anyway ... at least I now understand why you are using a nested loop now, and I understand the bug.

Hint 3: Even when a character appears multiple time in a string, it will still appear ZERO times after its last occurrence.

That is what your inner loop tests for. So what you are finding is the first character in the string that isn't duplicated in the remainder of the string.

The fix is simple ... once you understand what you are doing wrong.

---

Once you have fixed that are some other tidy ups:

• The else continue is redundant.

• The c variable is unnecessary ... if you change:

      if (flag==0){
          c = line.charAt(i);
          break;
      }
  

  to

      if (flag==0){
          return line.charAt(i);
      }
  

  and

      return c;
  

  to

      return null;
  

---

^{1 - This is what a native English speaker understands by "find the first non-repeating character". It is possible that you mean something else. If so, please update the question to clarify. Please describe as clearly as you can what you mean. Please give examples.}

Answer 5

***For all case of repetition

Character c = null;
    int strLength = line.length();

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

        int flag = 0;
        for (int j = 0; j < strLength; j++) {
            if (line.charAt(i) == line.charAt(j) && i != j) {
                flag = 1;
                break;
            }
        }

        if (flag == 0) {
            c = line.charAt(i);
            break;
        }

    }
    return c;

This is so simple to check, Your logic is complex. try this for immediate repeated character.

Character c = null;
        int strLength = line.length();

        for (int i = 0; i < strLength - 1;) {

            int flag = 0;
            int present_char_position = 0;

            if (line.charAt(i) == line.charAt(i + 1)) {
                flag++;
                present_char_position = i;
                i += 2;//jumping from those two character if matched
                continue;
            } else {
                present_char_position = i;
                i++;//if not matched go to next character
            }

            if (flag == 0) {
                c = line.charAt(present_char_position);
                break;
            }

        }
        return c;