Line 17: Char 20: runtime error: left shift of 1 by 31 places cannot be represented in type 'int' [solution.c] [closed]

You are correct that this left shift is an overflow when applied to the 1 literal. In C, literals are int, by default. However, your syntax uint64_t(1) is the wrong syntax for a cast in C.

Instead, if the type uint64_t exists, you can cast to it in the expression (uint64_t)1. C also defines¹ the UINT64_C macro (in all caps) which allows you to create an unsigned constant of width at least 64, which will always work. In this case it is best to do UINT64_C(1)

For example, (UINT64_C(1) << j) and ((uint64_t)1 << j) should both work.

¹ Thanks to @john-bollinger and this stackoverflow answer for pointing this out.

Your code is too complicated and the used algorithm is entirely unclear. To solve the problem there is no any need to use the function pow that deals with floating point numbers and the left shift operator. And creating a variable length array within the function makes it even more unsafe.

In my opinion your code just does not make sense relative to the decribed problem.

It is usually the case that any complicated code contains a bug.

All what you need is the standard C string function strchr.

I would write the function the following way.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isSubsequence( const char *s, const char *t ) 
{
    bool subsequence = true;
    
    while ( *s && ( subsequence = ( ( t = strchr( t, *s ) ) != NULL ) ) )
    {
        ++t;
        ++s;
    }
    
    return subsequence;
}

int main(void) 
{
    puts( isSubsequence( "abc", "ahbgdc" ) ? "true" : "false" );
    puts( isSubsequence( "axc", "ahbgdc" ) ? "true" : "false" );
}

The program output is

true
false

It is assumed that an empty string is always a substring of any other string.

The code is definitely too complicated and only works for short strings.

If the string has 31 characters, shifting 1 left by 31 positions shifts the bit into the sign bit, which has undefined behavior, if the shift count is 32 or larger (equal or larger than the width of the int type), the behavior is undefined too. You could use 1ULL << j but this would only work up to 63 characters, not enough for a reliable implementation.

There is a much simpler algorithm to check if s is a subsequence of t: all characters from s must be present in t in the same order.

Let's analyse this:

• the empty string is a subsequence of any string.
• if the first character of s is not present in t, not a subsequence.
• if it is, s can be a subsequence if the remainder of s is a subsequence of the remainder of t.

This can be implemented recursively:

#include <stdbool.h>
#include <string.h>

bool isSubsequence(const char *s, const char *t) 
{
    if (!*s)
        return true;
    t = strchr(t, *s);
    if (!t)
        return false;
    return isSubsequence(s + 1, t + 1);
}

You can pack this as a single expression, but less readable for no performance gain:

bool isSubsequence(const char *s, const char *t) 
{
    return *s ? (t = strchr(t, *s)) ? isSubsequence(s + 1, t + 1) : false : true;
}

Here is simple alternative as a loop:

#include <stdbool.h>
#include <string.h>

bool isSubsequence(const char *s, const char *t) 
{
    while (*s) {               // while there are more bytes in the pattern
        t = strchr(t, *s++);   // scan the string for the first occurrence
        if (!t)                // not found: not a subsequence, return failure
            return false;
        t++;                   // skip the byte found and continue
    }
    return true;               // all bytes found in sequence: return success
}

Here is a shorter but slightly less efficient iterative version:

#include <stdbool.h>
#include <string.h>

bool isSubsequence(const char *s, const char *t) 
{
    while ((t = strchr(t, *s++)) != NULL) {
        if (!*t++)
            return true;
    }
    return false;
}

Finally an iterative self contained implementation:

#include <stdbool.h>

bool isSubsequence(const char *s, const char *t) 
{
    char cs, ct;
    while ((cs = *s++) != '\0') {
        while ((ct = *t++) != cs) {
            if (ct == '\0')
                return false;
        }
    }
    return true;
}