Комбинации строкового алгоритма C#

Question

Итак, недавно у меня было интервью, в котором один из вопросов был таким, как показано ниже. Некоторое время я думал, как это решить. Кто-нибудь знает? Я выяснил, что это связано с алгоритмом комбинации строк.

Дано string, состоящее из 'x' и 'y'. Задача состоит в том, чтобы разбить его на 3 отдельные части, чтобы каждая часть содержала одинаковое число букв 'y'. Сколько способов может быть разделена строка.

Например:

Ввод: "xyxyy"

Выход: "xy | xy | y", "xyx | y | y"

Если кто может дайте мне какую-то подсказку о том, что мне нужно знать, чтобы понять это, или, что еще лучше, если вы покажете код, объясняющий, как это можно сделать, это будет здорово!

Спасибо

Answer 1

Подойдет простая математика. Итак, у вас есть строка с 3n 'y' (иначе вы вообще не сможете разделить строку). Строка выглядит примерно так:

 aybcdy ... eypq...raybcdy ...  eyvw..zybcdy ...  ey
 <--- n 'y'-->       <--- n 'y'-->     <--- n 'y'-->    

Обратите внимание, что фрагменты с y фиксированным, но символы между этими частями могут быть добавлены либо к одной части, либо к другой:

aybcdy ... ey | pq...raybcdy ...  ey # 1st possibility
<--- n 'y'-->          <--- n 'y'-->

aybcdy ... eyp | q...raybcdy ...  ey # 2nd possibility
<--- n 'y'-->          <--- n 'y'-->

aybcdy ... eypq | ...raybcdy ...  ey # 3d possibility
<--- n 'y'-->          <--- n 'y'-->

...

aybcdy ... eypq...ra | ybcdy ...  ey # the last possibility
<--- n 'y'-->          <--- n 'y'-->

Пока у нас есть (P + 1) * (Q + 1) возможностей разбить строку на 3 части, где

• P - символы между N -й и N+1 -ст 'y'
• Q - символы от 2N -го до 2N+1 -ст 'y'

Код:

private static int Solution(string value) {
  if (null == value)
    return 0;

  int N = value.Count(c => c =='y');

  if (N % 3 != 0 || N == 0) // let's return 0 if we don' have 'y's
    return 0;

  N = N / 3;

  int P = 0;
  int Q = 0;   
  int y = 0;

  foreach (char c in value) {
    if (c == 'y')
      y += 1;
    else if (y == N)
      ++P;
    else if (y == 2 * N) 
      ++Q;
  }

  return (P + 1) * (Q + 1);
}

Демо:

Console.Write(Solution("xyxyy")); 

Результат:

2

Если вы хотите получить сплиты:

private static IEnumerable<string[]> SolutionSplits(string value) {
  if (null == value)
    yield break;

  int N = value.Count(c => c == 'y');

  if (N % 3 != 0 || N == 0) // let's return empty if we don' have 'y's
    yield break;

  N = N / 3;

  List<int> P = new List<int>();
  List<int> Q = new List<int>();
  int y = 0;

  for (int i = 0; i < value.Length; ++i) {
    char c = value[i];

    if (c == 'y')
      y += 1;

    if (y == N)
      P.Add(i);
    else if (y == 2 * N)
      Q.Add(i);
  }

  foreach (int p in P)
    foreach (int q in Q)
      yield return new string[] {
        value.Substring(0, p + 1),
        value.Substring(p + 1, q - p),
        value.Substring(q + 1)}; 
}

Демо:

 string source = "xyxyy";
 
 Console.Write(string.Join(Environment.NewLine, SolutionSplits(source)
   .Select(items => string.Join(" | ", items)));

Результат:

 xy | xy | y
 xyx | y | y