First Not Repeating Character Code

Question

Here is the question: Write a solution that only iterates over the string once and uses O(1) additional memory, since this is what you would be asked to do during a real interview.

Given a string s, find and return the first instance of a non-repeating character in it. If there is no such character, return '_'.

And here is my code:

char firstNotRepeatingCharacter(char * s) {
int count;
for (int i=0;i<strlen(s);i++){
    count=0;
    char temp=s[i];
    s[i]="_";
    char *find= strchr(s,temp);
    s[i]=temp;
    if (find!=NULL) count++;  
    else return s[i];
}
if (count!=0) return '_';

}

I dont know what's wrong but when given an input: s: "abcdefghijklmnopqrstuvwxyziflskecznslkjfabe" the output is for my code is "g" instead of "d". I thought the code should have escaped the loop and return "d" soon as "d" was found. Thx in advance!!!

Answer 1

In your program, problem is in this statement-

s[i]="_";

You are assigning a string to a character type variable s[i]. Change it to -

s[i]='_';

At the bottom of your firstNotRepeatingCharacter() function, the return statement is under the if condition and compiler must be giving a warning for this as the function is supposed to return a char. Moreover, count variable is not needed. You could do something like:

char firstNotRepeatingCharacter(char * s) {
    for (int i=0;i<strlen(s);i++){
            char temp=s[i];
            s[i]='_';
            char *find= strchr(s,temp);
            s[i]=temp;
            if (find==NULL)
                    return s[i];
    }
    return '_';
}

But this code is using strchr inside the loop which iterates over the string so, this is not the exact solution of your problem as you have a condition that - the program should iterates over the string once only. You need to reconsider the solution for the problem.

May you use recursion to achieve your goal, something like - iterate the string using recursion and, somehow, identify the repetitive characters and while the stack winding up identify the first instance of a non-repeating character in the string. It's implementation -

#include <stdio.h>

int ascii_arr[256] = {0};

char firstNotRepeatingCharacter(char * s) {
    char result = '-';
    if (*s == '\0')
            return result;
    ascii_arr[*s] += 1;
    result = firstNotRepeatingCharacter(s+1);
    if (ascii_arr[*s] == 1)
            result = *s;
    return result;
}

int main()
{
        char a[] = "abcdefghijklmnopqrstuvwxyziflskecznslkjfabe";
        printf ("First non repeating character: %c\n", firstNotRepeatingCharacter(a));
        return 0;
}

In the above code, firstNotRepeatingCharacter() function iterates over the string only once using recursion and during winding up of the stack it identifies the first non-repetitive character. I am using a global int array ascii_arr of length 256 to keep the track of non-repetitive character.

Answer 2

Java Solution:

Time Complexity: O(n)

Space Complexity: with constant space as it will only use more 26 elements array to maintain count of chars in the input

Using Java inbuilt utilities : but for inbuilt utilities time complexity is more than O(n)

 char solution(String s) {
        char[] c = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            if (s.indexOf(c[i]) == s.lastIndexOf(c[i]))
                return c[i];
        }
        return '_';
    }

Using simple arrays. O(n)

char solution(String s) {

    // maintain count of the chars in a constant space
    int[] base = new int[26];
    
    // convert string to char array
    char[] input = s.toCharArray();
    
    // linear loop to get count of all
    for(int i=0; i< input.length; i++){
        int index = input[i] - 'a';
        base[index]++;
    }
    
    // just find first element in the input that is not repeated.
    for(int j=0; j<input.length; j++){
        int inputIndex = input[j]-'a';
        if(base[inputIndex]==1){
            
            System.out.println(j);
            return input[j];        
        }
    }
    
    return '_';
}