Check if strings contain the same number of the same characters

Question

Here is the problem we have to check if two strings contain the same characters, regardless of order. For example s1=akash s2=ashka match. My program is showing NO for every input strings; s1 and s2 are two input strings t is the number of testcases ->it would be really helpful if you can tell me where is the error I am a beginner

#include<stdio.h>
#include<string.h>
int main(){
int t,i,j;
scanf("%d",&t);
while(t>0){
    char s1[100],s2[100];
    scanf("%s ",s1);
    scanf("%s",s2);
    int count=0;
    int found[100];
    for(i=0;i<strlen(s1)-1;i++){
        for(j=0;j<strlen(s1);j++){
            if(s1[i]==s2[j]){
                found[i]=1;
                break;
            }


        }
    }
       for(i=0;i<strlen(s1);i++){
           if(found[i]!=1){
          count=1;
          break;

           }
       }
    if(count==1)
    printf("NO");
    else
    printf("YES");

 t--;
}



}

Answer 1

Some good answers above suggest sorting the strings first.

If you want to modify your program above to do this job then you need to modify it as you realised. I have a suggestion (in words) for how to do this below - after that there is a modified code that works, and finally a couple of extra points.

I guess that two strings aa and a would not be equal according to your definition, but your program would say that they were equal because once you find a character you do not have anyway of saying that it has been 'used up'

I would suggest that you change your found[] array so that it records when a character in the second string is matched.

I suggest logic as follows.

Loop through all S1 characters

| Loop through S2 charaters

| - if you get a match mark the S2 character as found

| - if you don't get a match by the end of the S2 loops then you are done - they are not equal

At the end of the S1 loop if you have not finished early then every character is matched, but you need to go through found[] array to check that every character in S2 was found.

working code is below....

note

• you did not initialize found - it is initialize below in code

• the first loop needs to have < strlen(s1) not < strlen(s1)-1

• the second loop you should have been going to strlen(s2).

• logic changed as described above so that found records characters found in s2 not s1

• logic also changed so that if a character in s1 is not found the loop breaks early. There are tests to see if the loop broke early to see if the values of i and j are what we expect at the end of the loop.

edited code below (at the bottom below the code are some extra comments)

#include<stdio.h>
#include<string.h>
int main(){
int t,i,j;
scanf("%d",&t);
while(t>0){
    char s1[100],s2[100];
    scanf("%s ",s1);
    scanf("%s",s2);
    int count=0;
    int found[100]={ 0 };
    for(i=0;i<strlen(s1);i++){
        for(j=0;j<strlen(s2);j++){
            if(found[j]==1) continue; // character S2[j] already found
            if(s1[i]==s2[j]){
                found[j]=1;
                break;
            }
        }
        if (j==strlen(s2)) {
            break;   // we get here if we did not find a match for S1[i]
        }
    }
    if (i!=strlen(s1)) {
        printf("NO"); // we get here if we did not find a match for S1[i]       
    } 
    else {
      // matched all of S1 now check S2 all matched
       for(i=0;i<strlen(s2);i++){
           if(found[i]!=1){
          count=1;
          break;

           }
       }
    if(count==1) {
      printf("NO"); 
   }
    else {
      printf("YES");
     }
 }
 t--;
}
return 0;
}

Two extra points to make your code more efficient.

• First, as suggested by @chux it will probably be faster not to have strlen(s2) in the condition for the loop. What you could have instead would be for (j=0;s2[j];j++). This works because the final character at the end of the string will have the value 0 and in C a value of 0 means false.. in the for loop the loop runs whilst the logic statement is true and when it is false the loop stops. The speed up of not using strlen[s2] in the loop is because the compiler might decide to calculate strlen[s2] each time you go through the loop, which means counting for l2 if l2 is the length of s2 - thus as you have to go through the two loops l1*l2 times potentially with the strlen counting you actually have l1*l2*l2 steps.

• secondly, you could speed up many tests by checking to see if the lengths of the two strings are different before checking if they contain the same number of the same types of character.

Answer 2

First, note that found is never initialized. The values within it are unknown. It ought to be initialized by setting every element to zero before each test for equality. (Or, if not every element, every element up to strlen(s1)-1, as those are the ones that will be used.)

Once found is initialized, though, there is another problem.

The first loop on i uses for(i=0;i<strlen(s1)-1;i++). Within this, found[i] is set if a match is found to s1[i]. Note that i never reaches strlen(s1)-1 within the loop, since the loop terminates when it does.

The second loop on i uses for(i=0;i<strlen(s1);i++). Within this loop, found[i] is tested to see if it is set. Note that i does reach strlen(s1)-1, since the loop terminates only when i reaches strlen(s1). However, found[strlen(s1)-1] can never have been set by the first loop, since i never reaches strlen(s1)-1 in the first loop. Therefore, the second loop would always report failure.

Additionally, it is not clear whether two strings ought to be considered equal if and only if they are anagrams (the characters in one can be rearranged to form the other string, without adding or removing any characters) or if each character in one string is found at least once in the other (“aaabbc” would be equal to “abbccc”, because both strings contain a, b, and c).

As written, with the initialization and loop bugs fixed, your program tests whether each character in the first string appears in the second string. This is not an equivalence relation because it is not reflexive: It does not test whether each character in the second string appears in the first string. So, you need to think more about what property you want to test and how to test for it.

Answer 3

Complicated solutions I did as a training. Two implementations controlled with a macro below.
First implementation loops through every character in the string, counts it's count in the first and second string and compares the values.
The second implementation allocates and creates a map of characters with count for each string and then compares these maps.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
#include <errno.h>

// configuration
#define STRCHARSETCNTCMP_METHOD_FOREACH  0
#define STRCHARSETCNTCMP_METHOD_MAP      1
// eof configuration

//#define dbgln(fmt, ...)  fprintf(stderr, "%s:%d: " fmt "\n", __func__, __LINE__, ##__VA_ARGS__)
#define dbgln(...)  ((void)0)


/**
 * STRing CHARacter SET CouNT CoMPare
 * compare the count of set of characters in strings
 * @param first string
 * @param the other string
 * @ret true if each character in s1 is used as many times in s2
 */
bool strcharsetcntcmp(const char s1[], const char s2[]);


// Count how many times the character is in the string
size_t strcharsetcntcmp_count(const char s[], char c)
{
    assert(s != NULL);
    size_t ret = 0;
    while (*s != '\0') {
        if (*s == c) {
            ++ret;
        }
        *s++;
    }
    return ret;
}

// foreach method implementation
bool strcharsetcntcmp_method_foreach(const char s1[], const char s2[])
{
    const size_t s1len = strlen(s1);
    const size_t s2len = strlen(s2);
    if (s1len != s2len) {
        return false;
    }
    for (size_t i = 0; i < s1len; ++i) {
        const char c = s1[i];
        const size_t cnt1 = strcharsetcntcmp_count(s1, c);
        const size_t cnt2 = strcharsetcntcmp_count(s2, c);
        // printf("'%s','%s' -> '%c' -> %zu %zu\n", s1, s2, c, cnt1, cnt2);
        if (cnt1 != cnt2) {
            return false;
        }
    }
    return true;
}


// array of map elements
struct strcharsetcntcmp_map_s {
    size_t cnt;
    struct strcharsetcntcmp_map_cnt_s {
        char c;
        size_t cnt;
    } *map;
};

// initialize empty map
void strcharsetcntcmp_map_init(struct strcharsetcntcmp_map_s *t)
{
    assert(t != NULL);
    dbgln("%p", t);
    t->map = 0;
    t->cnt = 0;
}

// free map memory
void strcharsetcntcmp_map_fini(struct strcharsetcntcmp_map_s *t)
{
    assert(t != NULL);
    dbgln("%p %p", t, t->map);
    free(t->map);
    t->map = 0;
    t->cnt = 0;
}

// get the map element for character from map
struct strcharsetcntcmp_map_cnt_s *strcharsetcntcmp_map_get(const struct strcharsetcntcmp_map_s *t, char c)
{
    assert(t != NULL);
    for (size_t i = 0; i < t->cnt; ++i) {
        if (t->map[i].c == c) {
            return &t->map[i];
        }
    }
    return NULL;
}

// check if the count for character c was already added into the map
bool strcharsetcntcmp_map_exists(const struct strcharsetcntcmp_map_s *t, char c)
{
    return strcharsetcntcmp_map_get(t, c) != NULL;
}

// map element into map, without checking if it exists (only assertion)
int strcharsetcntcmp_map_add(struct strcharsetcntcmp_map_s *t, char c, size_t cnt)
{
    assert(t != NULL);
    assert(strcharsetcntcmp_map_exists(t, c) == false);
    dbgln("%p %p %zu %c %zu", t, t->map, t->cnt, c, cnt);
    void *pnt = realloc(t->map, sizeof(t->map[0]) * (t->cnt + 1));
    if (pnt == NULL) {
        return -errno;
    }
    t->map = pnt;
    t->map[t->cnt].c = c;
    t->map[t->cnt].cnt = cnt;
    t->cnt++;
    return 0;
}

// create map from string, map needs to be initialized by init and needs to be freed with fini
int strcharsetcntcmp_map_parsestring(struct strcharsetcntcmp_map_s *t, const char s[])
{
    assert(t != NULL);
    assert(s != NULL);
    int ret = 0;
    while (*s != '\0') {
        const char c = *s;
        if (!strcharsetcntcmp_map_exists(t, c)) {
            const size_t cnt = strcharsetcntcmp_count(s, c);
            ret = strcharsetcntcmp_map_add(t, c, cnt);
            if (ret != 0) {
                break;
            }
        }
        ++s;
    }
    return ret;
}

// compare two maps if they have same sets of characters and counts
bool strcharsetcntcmp_cmp(const struct strcharsetcntcmp_map_s *t, const struct strcharsetcntcmp_map_s *o) 
{
    assert(t != NULL);
    assert(o != NULL);
    if (t->cnt != o->cnt) {
        return false;
    }
    for (size_t i = 0; i < t->cnt; ++i) {
        const char c = t->map[i].c;
        const size_t t_cnt = t->map[i].cnt;
        struct strcharsetcntcmp_map_cnt_s *o_map_cnt = strcharsetcntcmp_map_get(o, c);
        if (o_map_cnt == NULL) {
            dbgln("%p(%zu) %p(%zu) %c not found", t, t->cnt, o, o->cnt, c);
            return false;
        }
        const size_t o_cnt = o_map_cnt->cnt;
        if (t_cnt != o_cnt) {
            dbgln("%p(%zu) %p(%zu) %c %zu != %zu", t, t->cnt, o, o->cnt, c, t_cnt, o_cnt);
            return false;
        }
        dbgln("%p(%zu) %p(%zu) %c %zu", t, t->cnt, o, o->cnt, c, t_cnt);
    }
    return true;
}

// map method implementation
bool strcharsetcntcmp_method_map(const char s1[], const char s2[])
{
    struct strcharsetcntcmp_map_s map1;
    strcharsetcntcmp_map_init(&map1);
    if (strcharsetcntcmp_map_parsestring(&map1, s1) != 0) {
        abort(); // <insert good error handler here>
    }

    struct strcharsetcntcmp_map_s map2;
    strcharsetcntcmp_map_init(&map2);
    if (strcharsetcntcmp_map_parsestring(&map2, s2) != 0) {
        abort(); // <insert good error handler here>
    }

    const bool ret = strcharsetcntcmp_cmp(&map1, &map2);

    strcharsetcntcmp_map_fini(&map1);
    strcharsetcntcmp_map_fini(&map2);

    return ret;
}

bool strcharsetcntcmp(const char s1[], const char s2[])
{
    assert(s1 != NULL);
    assert(s2 != NULL);
#if STRCHARSETCNTCMP_METHOD_FOREACH
    return strcharsetcntcmp_method_foreach(s1, s2);
#elif STRCHARSETCNTCMP_METHOD_MAP
    return strcharsetcntcmp_method_map(s1, s2);
#endif
}

// unittests. Should return 0
int strcharsetcntcmp_unittest(void)
{
    struct {
        const char *str1;
        const char *str2;
        bool eq;
    } const tests[] = {
        { "", "", true, },
        { "a", "b", false, },
        { "abc", "bca", true, },
        { "aab", "abb", false, },
        { "aabbbc", "cbabab", true, },
        { "123456789012345678901234567890qwertyuiopqwertyuiopasdfghjklasdfghjklzxcvbnmzxcvbnm,./;", "123456789012345678901234567890qwertyuiopqwertyuiopasdfghjklasdfghjklzxcvbnmzxcvbnm,./;", true },
    { "123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890", "123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890", true },
    { "123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890", "1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678900", false },
    };
    int ret = 0;
    for (size_t i = 0; i < sizeof(tests)/sizeof(tests[0]); ++i) {
        const bool is = strcharsetcntcmp(tests[i].str1, tests[i].str2);
        if (is != tests[i].eq) {
            fprintf(stderr, 
            "Error: strings '%s' and '%s' returned %d should be %d\n", 
            tests[i].str1, tests[i].str2, is, tests[i].eq);
            ret = -1;
        }
    }
    return ret;
}

int main()
{
    return strcharsetcntcmp_unittest();
}

Answer 4

As suggested in my comment, and since it's now a bit more clear, an easy way to compare two multisets represented as strings is to:

1. Sort the two strings (easy using the qsort() standard function)
2. Compare the result (using the strcmp() standard function)

This will work since it will map both "akash" and "ashka" to "aahks", before comparing.

Answer 5

for(i=0;i<strlen(s1)-1;i++){
    for(j=0;j<strlen(s1);j++){
        if(s1[i]==s2[j]){
            found[i]=1;
            break;
        }


    }
}

I am not able to understand why are you using j<strlen(s1) is second loop.

I think simple solution will be sorting the characters alphabetically and comparing one by one in single loop.

Answer 6

Sort both the strings by using bubble sort or any other tech. you know , then simply compair both strings by using strcmp() function .