CODEWITHSUNDEEP
javastring
Shashank Singh
Shashank Singh

Reputation: 9

Efficiently find first repeated character in a string without using any additional data structure in one traversal

Given a string S. The task is to find the first repeated character in it. We need to find the character that occurs more than once and whose index of second occurrence is smallest. S contains only lowercase letters.

It is giving wrong output for input-'crg' output-? expected -'-1'

Here is my code-

private static Character first(String s)
    {
        String str ="";
        char c =(char)-1;
       // int flag=-1;
        char c1='\0';
       
        for(int i=0;i<s.length();i++)
        {
            char ch = s.charAt(i);
            if(str.indexOf(ch)==-1)
            str+=ch;
            else{
                c1=ch;
                break;
            }
        }
        
        if(s.equals(str))
        return c;
        else
        return c1;
    }

Upvotes: 0

Views: 921

Answers (3)

user4910279
user4910279

Reputation:

Try this.

private static int first(String s) {
    int[] codePoints = s.codePoints().toArray();
    int max = codePoints.length;
    for (int i = 0, p = 0, n = 0; i < max; p = n, ++i)
        if ((n = codePoints[i]) == p)
            return p;
    return -1;
}

and

System.out.println(Character.toString(first("絵文字も処理できる😊😊😁😂")));

output

😊

Upvotes: 0

Eklavya
Eklavya

Reputation: 18480

Rather trying return -1 or char, you can try to return index of String or -1, since -1 is not a valid Unicode character.

Here is a better solution using an int array for counting occurrence in the string, if found 2nd occurrence it will return the index or return -1.

  static int check(String str){
    int[] cnt= new int[26];
    for(int i = 0; i < str.length(); i++) {
      int v = str.charAt(i)-'a';
      cnt[v]++;
      if(cnt[v] > 1) {
        return i;
      }
    }
    return -1;
  }

Upvotes: 0

Henry
Henry

Reputation: 43758

(char)-1 is the same as \uffff, it will always be printed as ? because \uffff is not a valid unicode character.

Upvotes: 1

Related Questions