Для того, чтобы максимизировать число строк c, будем жадно по порядку набирать символы строки c, встречающиеся в строке s, так как в строке s эти символы так же идут по порядку.