# Finding first recurring letter in each string of a given set

First input is the number of strings ex: 5
Second input is a set of strings ex: hello world how are you

Output the letter in the string ex: 'l' in string 1

Below is my code:

#include <stdio.h>
#include <stdlib.h>

void find_first_recurring_letter(char **str,int r,int c);

int main()
{
int r,i;
printf("Enter the number of strings to be entered");
scanf("%d",&r);
/*dynamic allocation for str*/
char **str=(char**)malloc(r*sizeof(char*));
for(i=0;i<r;i++)
str[i]=(char*)malloc(50*sizeof(char));
for(i=0;i<r;i++)
{
printf("Enter the string %d",i+1);
gets(str[i]);
}
for(i=0;i<r;i++)
printf("%s\n",str[i]);
find_first_recurring_letter(str,r,50);
for(i=0;i<r;i++)
free(str[i]);
return 0;
}

void find_first_recurring_letter(char **str,int r,int c)
{
char *ptr,*sptr,ch[r];
int indx[r];
int i;
for(i=0;i<r;i++)
{
indx[i]=0;
ch[i]='\0';
for(ptr=&str[i][0];*ptr!='\0';ptr++)
{
for(sptr=&ptr[1];*sptr!='\0';sptr++)
{
if(*ptr==*sptr)
ch[i]= *ptr;
indx[i]=1;
}
}
}
for(i=0;i<r;i++)
{
if(ch[i]!='\0')
printf("'%c' in string %d\n",ch[i],indx[i]+1);
}

}


# Better names

The variable names are too short to be meaningful. It's common to use i as an index in for-loops, but r doesn't really tell us its purpose. Names like number_of_strings are self-descriptive, so we should use those.

# Unused variables

We never use c in find_first_recurring_letter, therefore we should remove the parameter altogether.

Strictly speaking, we also never use indx[i]. If ch[i] is '\0',indx[i]will be1(see "always use braces" below), and1 otherwise, so we can replace

        printf("'%c' in string %d\n",ch[i],indx[i]+1);


by

        printf("'%c' in string %d\n", ch[i], 2);


without changing the programs logic.

# Simpler pointer logic

Instead of ptr = &str[i][0], which is ptr = &(*(str[i])) use ptr = str[i]. Instead of sptr = &ptr[1], just use sptr = ptr.

Again, we could call them current and next or similar.

By the way, all indx[i] are 1 (see "unused variables" above and "always use braces" below). That doesn't sound right. Also keep in mind that variable length arrays are optional from C11 on.

# Get rid of additional memory

If we printf the recurring character, we can get rid of ch and indx:

            if(*ptr==*sptr)
printf("....");
indx[i]=1;


# Always use braces

Note that the code above contains a bug. indx[1] will be set to 1 regardless whether *ptr == *sptr. The indentation is misleading here.

You probably added indx[i] later and forgot the add the braces, so we should always use braces to make sure that bugs like this cannot happen.

If you don't want to use braces, use a code formatter. The indentation on the automatically formatted code will hint possible errors.

# Prefer late C99 declarations if possible

That way we can keep the scope of our variables short, e.g.

for(int i = 0; i < number_of_strings; ++i) {
for(char *current = str[i]; *current != '\0'; current++) {
for(char *next = current + 1; *next != '\0'; next++) {
if(*current == *next) {
printf("'%c' in string %d\n", *current, i);
}
}
}
}


It's now impossible to use next outside of its loop. Also, we should try to initialize our variables whenever possible.

# Use const type* for inputs that are not supposed to change

That way we cannot accidentally modify your input values, e.g.

str[i][k] = '\0'


would not compile if str was const char**.

# Check malloc's return

We should really check whether malloc returns NULL.

# Split functions

find_first_recurring_letter doesn't follow its name completely. We find the first recurring letter on a set of strings on a per-string basis. That sounds perfect for a split:

const char * find_first_recurring_letter(const char * haystack) {
for(const char * current = haystack; *current != '\0'; current++) {
for(const char * next = current + 1; *next != '\0'; next++) {
if(*current == *next) {
return current;
}
}
}
return NULL;
}

void find_first_recurring_letters(const char ** strings, int number_of_strings) {
for(int i = 0; i < number_of_strings; i++) {
const char * result = find_first_recurring_letter(strings[i]);

if(result) {
printf("'%c' in string %d\n", *result, i);
}
}
}


We can now use find_first_recurring_letter on any null-terminated string. We're able to reuse functionality. Note that both functions are very easy to check by hand.

• but is there a better way of solving this problem @Zeta – katty Feb 7 '18 at 11:59
• @katty there are other algorithms with $\mathcal O(n \log k)$ time and $\mathcal O(k)$ additional space (where k is the number of distinct characters), and a radix-like one with $\mathcal O(n)$ time and $\mathcal O(2 ^\text{sizeof(char)})$ space. But those are other algorithms. – Zeta Feb 7 '18 at 12:14

@Zeta's answer is very good but I'd go ahead and improve the code by creating a few functions to improve readability:

void allocMemoryForStrings(char** arrayOfStrings, int numOfStrings){
for(int i = 0; i < numOfStrings; i++){
arrayOfStrings[i] = malloc(sizeof(*arrayOfStrings[i]) * 50);
}
}

void printStrings(char** arrayOfStrings, int numOfStrings){
for(int i = 0; i < numOfStrings; i++){
printf("%s\n", arrayOfStrings[i]);
}
}

void freeStrings(char** arrayOfStrings, int numOfStrings){
for(int i = 0; i < numOfStrings; i++){
free(arrayOfStrings[i]);
}
}


P.S.: The code might need some tweaks to compile/work. Use it as a reference.

• "some tweaks"? You didn't rename str or r in your second and third example, and i wasn't declared at all. – Zeta Feb 7 '18 at 16:19
• @Zeta you're absolutely right. I've corrected that and also changed the function names to cameCase. – luizfzs Feb 7 '18 at 18:07
• arrayOfStrings[i] = (char*) malloc(50 * sizeof(char)); ---> cast not needed. Also, consider using the size of the reference type and not an explicit type.: arrayOfStrings[i] = malloc(sizeof *arrayOfStrings[i] * 50);. Easy to code. review and maintain. – chux - Reinstate Monica Feb 7 '18 at 19:25
• @luizfzs Curious, do you find sizeof(*arrayOfStrings[i]) easier to read than without parens: sizeof *arrayOfStrings[i]? – chux - Reinstate Monica Feb 8 '18 at 15:03
• @chux, I find it easier to get what is being sizeof`'ed. – luizfzs Feb 8 '18 at 15:17