注：从输入和输出的集合中，我认为个别字符串的排列不应该被考虑。
如果有人能帮忙解决这个问题将不胜感激。谢谢。
adddddddddddddddddb）；
2. 它是一个后缀、仅由该字符组成的字符串集合和一个前缀的连接。在这种情况下，不能重复使用任何字符串，包括字符作为同一个字符串的后缀和前缀的情况。（为了避免重用同类字符串，后缀和前缀必须严格，即不能是整个字符串）。O(1)；由于我们处理的字符数不能大于所有字符串中的总字符数，哈希表的大小要求可以被认为是 O(N)。（实际上，它受到字母表大小的限制，因此与固定大小的数组一样，存储要求在技术上是 O(1)，但在 Unicode 等情况下，常数相当大）。maximum_sum = max(maximum_sum,
prefix_length + maximum_suffix,
suffix_length + maximum_prefix)
maximum_prefix = max(maximum_prefix, prefix_length)
maximum_suffix = max(maximum_suffix, suffix_length)
homogeneous_length，maximum_sum，maximum_prefix，maximum_suffix。在扫描结束时，我们需要找到homogenous_length + maximum_sum最大的字符；我们可以通过简单地扫描字符表来实现这一点。O(1)（对于初始扫描），这是O(N)（其中N是问题中所有字符的总数），加上对字符表进行最终扫描的O(max(N, |A|))（其中|A|是字母表的大小）；换句话说，O(N)。请参考上面的空间要求。 #include <iostream>
using namespace std;
class alphabet
{
string str;
int chars[26];
public:
alphabet()
{
for(int i=0; i < 26 ; i++)
chars[i] = 0;
}
void initialize(string s)
{
str = s;
for(int pos=0 ; pos < s.length(); pos++)
chars[s[pos]-'a']++;
}
int getCount(int i)
{
return chars[i];
}
};
int main()
{
int n=3;
alphabet *arr = new alphabet[n];
arr[0].initialize("varun");
arr[1].initialize("ritl");
arr[2].initialize("hello");
int Max =0;
char MaxChar = ' ';
for(int i=0; i<n-1 ; i++)
{
for(int j=0; j<26; j++)
{
int m = arr[i].getCount(j)+ arr[i+1].getCount(j);
if(m > Max)
{
Max = m;
MaxChar = char('a' + j);
}
}
}
cout<<"Max Char = "<<MaxChar<<" "<<Max<<" times";
system("pause");
}
步骤1：需要维护4个表，每个表的长度为26 --第一个表跟踪字符串中最长前缀的长度 --第二个表跟踪字符串中最长后缀的长度 --第三个表跟踪完全由给定字符组成的字符串的总长度 --第四个表跟踪中间最长的字符
步骤2： --循环运行0到26，并将first[i]+second[i]+third[i]添加到sum[i]中并存储它们 --在sum[i]和fourth表中找到最大元素。 --索引是字母（0是A），最大的元素是长度
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int pre[26],su[26],single[26],middle[26],sum[26];
int getlength(char str[][10])
{
int i,j,n=3,counter=0,max=-1,index;
char c,p;
for(j=0;j<n;j++)
{
for(i=0;i<strlen(str[j]);i++)
{
if(i==0)
{
c=str[j][i];
counter++;
continue;
}
else if(i==strlen(str[j])-1&&c == str[j][i])
{
counter =0;
break;
}
else
{
if(c == str[j][i])
counter++;
else
break;
}
}
if(pre[toupper(c)-65]<counter)
pre[toupper(c)-65]=counter;
counter=0;
}
for(j=0;j<n;j++)
{
for(i=strlen(str[j])-1;i>=0;i--)
{
if(i==strlen(str[j])-1)
{
c=str[j][i];
counter++;
continue;
}
else if(i==0&&c == str[j][i])
{
counter =0;
break;
}
else
{
if(c == str[j][i])
counter++;
else
break;
}
}
if(su[toupper(c)-65]<counter)
su[toupper(c)-65]=counter;
counter=0;
}
for(j=0;j<n;j++)
{
for(i=strlen(str[j])-1;i>=0;i--)
{
if(i==strlen(str[j])-1)
{
c=str[j][i];
counter++;
continue;
}
else
{
if(c == str[j][i])
counter++;
else
{
counter=0;
break;
}
}
}
if(single[toupper(c)-65]<counter)
single[toupper(c)-65]=counter;
counter=0;
}
counter=0;
for(j=0;j<n;j++)
{
for(i=1;i<strlen(str[j])-1;i++)
{
if(i==1)
{
c=str[j][i];
counter++;
}
else
{
if(c == str[j][i])
{
counter++;
}
else
{
if(middle[toupper(c)-65]<counter)
middle[toupper(c)-65]=counter;
counter=1;
c=str[j][i];
}
}
}
counter=0;
}
for(i=0;i<26;i++)
{
sum[i]=pre[i]+su[i]+single[i];
if(sum[i]>max)
{
max=sum[i];
index=i;
}
}
for(i=0;i<26;i++)
{
if(middle[i]>max)
{
max=middle[i];
index=i;
}
}
printf("\n length %d index %d",max,index);
}
void main()
{
char arr[3][10]={"bbbb","dccccccar","vaa"};
getlength(arr);
}
这是我天真的 Ruby 实现。我将尝试解释我的思路和实现过程。
在 Ruby 中，字符串不是可枚举的，因此 Ruby 无法像 Python 那样直接枚举它。这就是 str.chars.to_a 的作用。它将字符串转换为字符数组。
我的计划是计算每个字符串中每个字符出现的次数。例如，["ab", "ba", "ccc"] 将变成 [{"a"=>1, "b"=>1}, {"b"=>1, "a"=>1}, {"c"=>3}]。然后，我会添加每个连续的哈希/字典对的出现次数。在这个例子中，它将得到 [{"a"=>2, "b"=>2}, {"b"=>1, "a"=>1, "c"=>3}]。这个哈希数组中最高的值将代表最长的连续序列。
max_running_sequence方法中的arr_of_chararr.each中实现。Hash#merge和块实现，除了数组中只有一个元素的特殊情况。class Sequence_tester
def self.max_running_sequence(arr_of_chararr)
reduced = []
all_same_chars = []
arr_of_chararr.each do |str|
arr = str.chars.to_a
if arr.all? {|c| c == arr.first}
all_same_chars += arr
else
if !all_same_chars.empty?
if arr.any? {|c| c == all_same_chars.first}
arr += all_same_chars
else
reduced << count_char_occurrences(all_same_chars)
end
end
reduced << count_char_occurrences(arr)
all_same_chars.clear
end
end
if !all_same_chars.empty?
reduced << count_char_occurrences(all_same_chars)
end
max_seqs = reduced
if reduced.length > 1
max_seqs = reduced.each_cons(2).map do |pair|
pair.first.merge(pair.last) {|key, oldval, newval| oldval + newval}
end
end
longest_seq = max_seqs.map {|h| h.max_by {|kv| kv[1]} }.max_by {|a| a[1]}
end
def self.count_char_occurrences(arr)
arr.each_with_object(Hash.new(0)) {|o, h| h[o] += 1}
end
end
input = ["a", "b", "c"]
res = Sequence_tester.max_running_sequence(input)
puts "#{res.first},#{res.last}"
input = ["abc", "abb", "abc"]
res = Sequence_tester.max_running_sequence(input)
puts "#{res.first},#{res.last}"
input = ["ab", "ba", "ccc"]
res = Sequence_tester.max_running_sequence(input)
puts "#{res.first},#{res.last}"
input = ["ada", "dd", "dd", "eedd"]
res = Sequence_tester.max_running_sequence(input)
puts "#{res.first},#{res.last}"
输出：
a，1
b，3
c，3
d，7
你可以使用哈希表来实现。最慢的算法是为每个字符串创建一个字符计数器的映射，然后找到最大值。
我也想了解更高级的算法。
var set = new List<string>() { "ab", "ba", "aac" };
2.) 我组装了一个通用的方法来递归地组装所有排列。
private static List<List<T>> GetPermutations<T>(List<T> values)
{
if (values.Count <= 1) return new List<List<T>>() { values };
var results = new List<List<T>>();
var perms = GetPermutations(values.Skip(1).ToList());
foreach (var perm in perms)
{
foreach (int i in Enumerable.Range(0, perm.Count + 1))
{
List<T> list = new List<T>();
list.AddRange(perm.Take(i));
list.Add(values[0]);
list.AddRange(perm.Skip(i));
results.Add(list);
}
}
return results;
}
3.) 我找到了该集合的所有排列。
var perms = GetPermutations<string>(set);
4.) 我定义了一个方法来查找单个字符串中最长的连续序列。
private static string LongestRunningSequence(string s)
{
if (string.IsNullOrEmpty(s)) return null;
if (s.Length == 1) return s;
var seq = new Dictionary<char, int>();
char prev = s[0];
int counter = 0;
foreach (char cur in s)
{
if (cur == prev) // chars match
{
++counter; // increment counter
}
else // chars don't match
{
prev = cur; // store new char
counter = 1; // reset the counter
}
// store the higher number of characters in the sequence
if (!seq.ContainsKey(prev)) seq.Add(prev, counter);
else if (seq[prev] < counter) seq[cur] = counter;
}
char key = seq.Keys.First();
foreach (var kvp in seq)
{
if (kvp.Value > seq[key]) key = kvp.Key;
}
return string.Join("", Enumerable.Range(0, seq[key]).Select(e => key));
}
5.) 我定义了一个方法，它可以在字符串列表中找到最长的连续序列，并利用之前针对单个字符串执行此操作的方法。
private static string LongestRunningSequence(List<string> strings)
{
string longest = String.Empty;
foreach (var str in strings)
{
var locallongest = LongestRunningSequence(str);
if (locallongest.Length > longest.Length) longest = locallongest;
}
return longest;
}
6.) 我将每个计算出的排列表示为由单个字符串组成的列表。
var strings = perms.Select(e => string.Join("", e)).ToList();
7.) 我将这个列表传递给之前的方法，该方法在字符串列表中查找最长运行序列。
LongestRunningSequence(strings); // returns aaa