I am trying to write a bool function that checks if the string input has any duplicate characters

user_17718482 0
Viewed 63

I wrote this function under main I want to check if the string input has any duplicate characters but when I used the debug feature it turns out that the outer loop only loops once while the inner loop loops correctly. I don't know why the outer loop shouldn't iterate as many times as the length of the string ?,, im sorry i ran into another problem the program needs to be case insensitive to i tried integrating tolower in the bool function but it does not work for some reason ,yes its a cs50 task

#include <cs50.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
bool only_letters(string s);
bool duplicts(string b);
int main(int argc, string argv[])
{
    if(argc!=2){
        printf("wrong input\n");
        return 1;
    }
    int length=strlen(argv[1]);
    if(length!=26){
        printf("Key must contain 26 characters.\n");
        return 1;
    }
    if(!only_letters(argv[1])){
        printf("key must contain only alphapetic letters.\n");
        return 1;
    }
    if(!duplicts(argv[1])){
        printf("key must not contain same characters\n");
        return 1;
    }
}
// need a check input function if letters or not
bool only_letters(string s){
    int length=strlen(s);
    for(int i =0;i<length;i++){
if(!isalpha(s[i]))
     return false;
    }return true;
}
bool duplicts(string b) {
    int length = strlen(b);
    for (int i = 0; i < length; i++) {
        for (int k = i + 1; k < length; k++) {
            tolower(b[i]);
            tolower(b[k]);
            if (b[i] == b[k])
                return false;
        }
    }
    return true;
}
cs50 c
1 Answers

Reformating your code with a sensible indentation convention makes the mistake obvious:

bool duplicts(string b) {
    int length = strlen(b);
    int count = 0;
    for (int i = 0; i < length; i++) {
        for (int k = 1; k < length; k++) {
            if ((b[i]) == b[k])
                count++;
        }
        return count;
    }
    if (count > 0) {
        return false;
    }
    return true;
}

The return count; is inside the outer loop, hence it only iterates once.

There is another problem: the inner loop should start at k = i + 1 otherwise you will always find duplicates in strings of more than 1 byte.

Your code can be easily modified to return false as soon as a duplicate character has been found:

bool duplicts(string b) {
    int length = strlen(b);
    for (int i = 0; i < length; i++) {
        for (int k = i + 1; k < length; k++) {
            if (b[i] == b[k])
                return false;
        }
    }
    return true;
}

You can further simplified to avoid calling strlen and handle arbitrary large strings (albeit very inefficiently):

bool duplicts(const char *s) {
    for (; *s != '\0'; s++) {
        for (size_t k = 1; s[k] != '\0'; k++) {
            if (s[k] == *s)
                return false;
        }
    }
    return true;
}

To fix the quadratic complexity which is inefficient for large strings, you can use an array:

bool duplicts(const char *s) {
    unsigned char seen[256] = { 0 };
    unsigned char c;
    while ((c = *s++) != '\0') {
        if (seen[c] != 0)
            return false;
        seen[c] = 1;
    }
    return true;
}
user_45932670
Related