В чём ошибка? Какие лишние подстроки находит мой алгоритм?

Question

[OrdUs]

Задачу можно найти тут по номеру 3763.
Свой алгоритм попытался объяснить комментариями в коде, надеюсь, их достаточно для его понимания.

using Microsoft.VisualBasic;
using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Net;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Text;
using System.Text.RegularExpressions;
using System.Xml;
using static System.Math;
using static System.Runtime.InteropServices.JavaScript.JSType;

namespace Solution
{
    class MAIN
    {
        static int ValidSubstringsCount(string input) //Возвращает количество подстрок длиной >2 символов
        {
            //Как будто что-то не так именно с этим методом, но в то же время на простейших примерах он вроде как верно работает
            int output = 0;
            for (int i = 0, length = input.Length - 2; i < length; i++)
            {
                output += length - i;
            }
            return output;
        }


        static string LastOneCharSubstring(string input, int end_index) //Возвращает наибольшую подстроку, заканчивающуюся на индексе end_index, из одинаковых символов (например LastOneCharSubstring("CAAABC", 3) возвращает "AAA")
        {
            char last_symb = input[end_index];
            int start_index = end_index;
            while (start_index != 0)
            {
                if (input[--start_index] != last_symb) return input.Substring(start_index+1, end_index-start_index);
            }
            return input.Substring(0, end_index + 1);
        }


        static void Main()
        {
            string? input; //Входная строка
            using (StreamReader file = new StreamReader(@"[Путь к файлу]")) //input получает значение
            {
                    input = file.ReadLine();
                    if (input == null) return;
            }


            List<string> valid_strings = new List<string>(); //"Основные" подстроки. Все остальные подходящие подстроки, так или иначе, будут подстроками этих подстрок, количество коих можно найти с помощью ValidSubstringsCount. Это и происходит в конце.

            bool contains_A = false;
            bool contains_B = false;
            bool contains_C = false;

            string cur_string = "";
            /*
             * Суть алгоритма:
             * Если cur_string уже содержит две уникальных буквы из трёх, а символ с индексом i является третей уникальной буквой, cur_string добавляется в valid_strings (только если её длина больше 2), 
             * после чего cur_string присваивается значение [наибольшая заканчивающаяся на индексе i подстрока из двух уникальных символов (например, "BBBC")].
             * В противном случае к cur_string просто добавляется input[i].
             */
            for (int i = 0, length = input.Length; i < length; i++) 
            {
                if (input[i] == 'C')
                {
                    if (contains_A && contains_B)
                    {
                        if (cur_string.Length > 2) valid_strings.Add(cur_string);
                        cur_string = LastOneCharSubstring(input, i-1) + "C";

                        contains_A = cur_string[0] == 'A' ? true : false;
                        contains_B = cur_string[0] == 'B' ? true : false;
                        contains_C = true;
                    }
                    else
                    {
                        cur_string += input[i];
                        contains_C = true;
                    }
                }

                if (input[i] == 'B')
                {
                    if (contains_A && contains_C)
                    {
                        if (cur_string.Length > 2) valid_strings.Add(cur_string);
                        cur_string = LastOneCharSubstring(input, i - 1) + "B";

                        contains_A = cur_string[0] == 'A' ? true : false;
                        contains_B = true;
                        contains_C = cur_string[0] == 'C' ? true : false;
                    }
                    else
                    {
                        cur_string += input[i];
                        contains_B = true;
                    }
                }

                if (input[i] == 'A')
                {
                    if (contains_B && contains_C)
                    {
                        if (cur_string.Length > 2) valid_strings.Add(cur_string);
                        cur_string = LastOneCharSubstring(input, i - 1) + "A";

                        contains_A = true;
                        contains_B = cur_string[0] == 'B' ? true : false;
                        contains_C = cur_string[0] == 'C' ? true : false;
                    }
                    else
                    {
                        cur_string += input[i];
                        contains_A = true;
                    }
                }
            }

            int output = 0;
            foreach (string s in valid_strings) output += ValidSubstringsCount(s);
            Console.WriteLine(output); //По идее, ответ

            foreach (string s in valid_strings) if ((s.Contains('A') && s.Contains('B') && s.Contains('C')) || !input.Contains(s) || (s.Length < 3)) Console.WriteLine($"Лишняя строка: {s}"); //Мои попытки найти ошибку. Безуспешные. Если valid_strings содержит лишнюю строку, по идее это должно её найти (но не находит)

        }
    }
}

Программа выводит ответ 261151 вместо требуемого 252776. Т.е. она находит какие-то лишние подстроки.

Answer 1

[Роман]

Пошаговая отладка вам в помощь.