Getting timeout error for increasing array size [closed]-CodePudding

Closed. This question needs

My program:

My Program is failing one test case. In this test case, 2 strings are given of length 10^6.

But my program can only accept length<=9999. If I increase the length in declaration I'm Getting the output is as follows

CodePudding user response：

Your approach has too many nested loops where you iterate over the input strings again and again. Your approach seems to be O(N^2) which is a problem when N gets huge.

I think you shall make a map (i.e. array with 256 elements) where you register which char values that a string contain. Something like:

int map_a[256] = { 0 };
for (int i = 0; i < strlen(s);   i)
{
    map_a[(unsigned char)s[i]]) = 1;
}

When you have made the map for both strings, you can simply compare the two maps and do the counting. Something like:

for (int i = 0; i < 256;   i)
{
    if (map_a[i] == 1 && map_b[i] == 1)
    {
        // character present in both strings
    }
    else if (map_a[i] == 1 || map_b[i] == 1)
    {
        // character only in one string
    }
}

This approach will be O(N) so it will scale better as N increase.

Note: This approach assumes 8 bit chars.

Page link：https//www.codepudding.com/Enterprise/119709.html

Prev:Transpose a matrix giving me error when column>row

Next:how to get case number for jump table from a switch statement

Tags：

string

runtime-error

large-data

Links：
CodePudding