Сопоставление и удаление подстрок повторяющихся символов, а затем возврат длины самой длинной подстроки
В качестве примера у меня есть случайная строка (я полагаю, регистр букв не имеет значения): "aqaswasldkaslfaslyetdop".
Мне нужно создать метод, который принимает строку в качестве аргумента, затем создает новую строку с отдельными символами только из входной строки и возвращает длину самой длинной подстроки, состоящей из символов, которые, кроме того, появляются во входной строке более одного раза. вышеупомянутая новая строка:
«aqaswasldkaslfaslyetdop» —> «qwkfaslyetdop»
int resultLength = GetMaxLengthOfDuplicateSubstring("aqaswasldkaslfaslyetdop", out string resultString);
Console.WriteLine($"{resultString}\nTHE LENGTH OF THE LONGEST DELETED SUBSTRING: {resultLength}");
// OUTPUT:
//
// qwkfaslyetdop
// THE LENGTH OF THE LONGEST DELETED SUBSTRING: 4
Я попытался найти набор повторяющихся символов.
var example = "qwasldkfaslyetdop";
var matchStrings = new string[example.Length];
var distinctStrings = new List<string>();
for (int index = 0; index < example.Length; index = index + 1)
{
matchStrings[index] = example[index].ToString();
if (Regex.Matches(example, matchStrings[index]).Count > 1)
{
distinctStrings.Add(matchStrings[index]);
}
}
distinctStrings = distinctStrings.Distinct().ToList();
foreach (string element in distinctStrings)
{
Console.WriteLine(element);
}
Но из-за всех этих перестановок, таких как "a", "s", "l", "d", "as", "sa", "asl", "sal", "sla", "lsa", "als", "las", "asld", ... я просто потерял первоначальную идею, как решить эту проблему.
Я не знаю, почему преподаватель из частной онлайн-школы сделал такое сложное упражнение, я уже с ним сбился. Я пробовал также позитивный просмотр вперед/назад, но без особого успеха.
Есть ли какие-либо ограничения на тип символов в вашей строке? Пунктуация, пробелы, неанглийские буквы....?
Вы отметили это regex. Означает ли это, что эту проблему следует решить с помощью регулярных выражений? Вы получили эту инструкцию?
Почему в вашем примере это не «aqaswasldkaslfaslyetdop» или «aqaswasldkaslfaslyetdop»? Я не понимаю, почему здесь «аслд» особенный.
Почему вам нужно использовать регулярное выражение?
@canton7 a,s,l,d появляются более одного раза.
@shingo Если это просто удаление повторяющихся символов, почему это не «aqaswasldkaslfaslyetdop»?
@canton7 Canton7 Я думаю, это следует понимать как удаление излишне повторяющихся символов. Например, что делает Distinct.
@shingo Да, именно поэтому я и спрашиваю — гадать, что означает вопрос, никогда не будет хорошим решением!
@DuesserBaest — не будет работать, мы просто считаем появление дублирующихся символов в строке в целом, но нам нужна подстрока там, где они расположены рядом, насколько я понимаю ваш алгоритм, мистер Баест, но у меня есть кое-что на уме, получилось Когда я последний час был на улице со своими индейками, это ужасно неэффективно с точки зрения вычислений, но я попробую реализовать.
@trincot К сожалению, учительница ничего не пояснила о том, какие символы могут быть в тексте задачи, как и о перестановках, поэтому я упрощаю себе задачу, предполагая, что это только буквы...
@trincot Потому что я пытался решить проблему с классом Regex, но пока не удалось. Это потому, что существует тег «регулярное выражение». Я ошибался?
@shingo — Это не так просто. Мы можем удалить дубликаты с помощью Distinct(), он фактически использовался в приведенном выше примере, но как тогда мы можем посчитать длину соответствующей подстроки? Сначала мы должны сопоставить эту подстроку... И это для меня большая проблема из-за перестановок.
Ответы 2
Объяснение:
1a) создайте набор повторяющихся символов в строке.
1b) удалите все символы из этого набора из вашей строки.
2a) создайте список из 1 и 0 длины исходной строки; 1, если буква в наборе, 0 иначе.
2b) затем запустите накопительную сумму, которая сбрасывается до 0, когда происходит 0 (00110100111) -> (00120100123).
2c) найдите максимум из этого списка.
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static Dictionary<char, int> ListToCountDict(List<char> l)
{
Dictionary<char, int> counts = new Dictionary<char, int>();
foreach (char item in l)
{
if (counts.ContainsKey(item))
{
counts[item]++;
}
else
{
counts[item] = 1;
}
}
return counts;
}
static void Main()
{
string str = "aqaswasldkaslfaslyetdop";
var duplLetters = new HashSet<char>(ListToCountDict(str.ToList()).Where(kvp => kvp.Value > 1).Select(kvp => kvp.Key));
string resS = new string(str.Where(s => !duplLetters.Contains(s)).ToArray());
List<int> binaryDup = str.Select(s => duplLetters.Contains(s) ? 1 : 0).ToList();
int max = 0;
int cur = 0;
foreach (int b in binaryDup)
{
if (b == 0)
{
cur = 0;
}
else
{
cur += b;
}
if (cur > max)
{
max = cur;
}
}
Console.WriteLine($"Result String: {resS}, Max: {max}");
}
}
Принты: Result String: qwkfyetop, Max: 4
да, пробовал в programiz
Неправильный ответ, потому что если у нас есть «JKLOJMK», мы должны получить «LOJMK», а не «LOM». В любом случае спасибо за попытку... Я постараюсь прочитать ваш ответ и, возможно, я там смогу что-то полезное.
abcdxabcxacxa вернет 9 для максимальной длины удаленной подстроки, что кажется неверным.
@ЯрославПархоменко, пожалуйста, уточните свой вопрос! В «JKLOJMK» дубликаты — «JK», поэтому я ожидаю в результате «LOM».
Да, согласен, вопрос не ясен. Я также ожидал бы LOM в результате того, как написан вопрос.
@MatthewWatson, почему? Насколько я понимаю, все дубликаты должны быть удалены - сохраняется только d. тогда длинная последовательность равна 9: xabcxacxa
@DuesserBaest — в примере внутри сообщения с вопросом довольно ясно: «aqaswasldkaslfaslyetdop» -> «qwkfaslyetdop» должно быть таким.
@ЯрославПархоменко Это очень НЕ понятно - вот почему в этом столько путаницы!
@ЯрославПархоменко, пожалуйста, отредактируйте свой вопрос, чтобы ПРОЯСНИТЬ, ПОЧЕМУ «aqaswasldkaslfaslyetdop» -> «qwkfaslyetdop». Я не получаю это сопоставление на основе вашего текущего объяснения.
@DuesserBaest — «Вся созданная из них подстрока» должна быть удалена, как я указал в вопросе. «Они» означают дубликаты, и чтобы прояснить это, я привел пример. Я думал этого достаточно, но из-за моего плохого английского...
@ЯрославПархоменко "qwkfaslyetdop", например, основан на более раннем "aqaswasldkaslfaslyetdop". так как же это может быть решением? или что мне не хватает?
@DuesserBaest Вы правы, я неправильно понял вопрос.
@DuesserBaest «qwkfaslyetdop» — может быть решением для «aqaswasldkaslfaslyetdop», поскольку мы создали новую строку с разными символами, жирный шрифт используется для символов, которые встречаются в исходной строке более одного раза.
@ЯрославПархоменко Теперь я понимаю, что ты ищешь. Если хотите, я могу оставить вам этот ответ, иначе я удалю его, так как он не решает вашу проблему.
@DuesserBaest Не удаляйте, пожалуйста, мне нужно сначала прочитать и понять.
@DuesserBaest Я считаю, что идея с собирательной суммой очень гениальна! По крайней мере пока я так думаю... Так что попробую воспользоваться. Но я никогда не работал с собирательными суммами, поэтому не понимаю, как они вычисляются, я имею в виду для всего списка? Или для близлежащих элементов?
@ЯрославПархоменко, ты перемещаешься по списку. когда вы встречаете 0, вы сбрасываете текущий счетчик. когда вы встречаете 1, вы добавляете 1 к текущему счетчику и проверяете, превышает ли он предыдущий максимум.
@DuesserBaest Слишком плохо, я не могу выбрать два ответа как правильные. Но я воспользуюсь собирательной суммой и некоторой логикой из решения Mr. canton7, чтобы закончить этот ПРОКЛЯТЫЙ ТЕСТ! Спасибо.
не беспокойся. не забудьте также проголосовать за ответ @canton7
Что-то вроде этого?
int GetMaxLengthOfDuplicateSubstring(string input, out string result)
{
var seen = new HashSet<char>();
int maxRemoveLength = 0;
int currentRemoveLength = 0;
var resultBuilder = new List<char>();
foreach (char c in input.Reverse())
{
if (seen.Add(c))
{
currentRemoveLength = 0;
resultBuilder.Add(c);
}
else
{
currentRemoveLength++;
maxRemoveLength = Math.Max(maxRemoveLength, currentRemoveLength);
}
}
result = string.Concat(resultBuilder.AsEnumerable().Reverse());
return maxRemoveLength;
}
Мы просматриваем строку задом наперед, записывая каждый символ, который мы видели. Если мы достигаем символа, который мы видели раньше, мы удаляем его из результата и ведем текущий подсчет количества символов, которые мы удалили в этой непрерывной последовательности.
А как посчитать длину самой длинной подстроки, составленной из повторяющихся символов, стоящих вместе? Как в примере выше.
Мы делаем это, как показано в моем коде, с currentRemoveLength для отслеживания длины текущей удаляемой подстроки и maxRemoveLength для отслеживания максимальной длины таких подстрок. Вы увидите, что он возвращает правильное значение, если щелкнете ссылку внизу моего ответа.
В вашем алгоритме, господин Кантон, мы считаем длину подстроки, составленной из удаленных символов, насколько я понимаю, а это не так. Нам нужна длина подстроки, состоящей из таких символов, например 'ALSAOLXAOPL' —> 'SXAOPL', LENGTH: 3 Или я что-то упустил... О_о
Ввод «ALSAOLXAOPL» возвращает 3. Используйте ссылку в моем вопросе, чтобы запустить код в Интернете, а затем замените «aqaswasldkaslfaslyetdop» на «ALSAOLXAOPL» в первой строке. На правой панели вы можете видеть, что код возвращает 3.
@ЯрославПархоменко Ты следишь? Это совокупный подсчет, аналогичный ответу ДюссертБерта, но логика удаления повторяющихся символов значительно проще.
— Я начинаю понимать! Спасибо и вам, мистер Кантон!
Я не знаю
c#, но возможно: 1a) создать в строке набор повторяющихся символов. 1b) удалите все символы из этого набора из вашей строки. 2a) создайте список из 1 и 0 длины исходной строки; 1, если буква в наборе, 0 иначе. 2b) затем запустите накопительную сумму, которая сбрасывается до 0, когда происходит 0 (00110100111) -> (00120100123). 2c) найдите максимум из этого списка.