找出字符串中最大子串的长度(要求子串中的字符不重复)
时间:2010-10-08 来源:chenping2008
给定一个字符串,找出这个字符串中的最大的子串的长度,要求这个子串中的字符不重复。下面贴出的是算法,和测试代码。
算法如下:
public Int32 GetSubCount(String str)
{
if (str == null)
{
return 0;
}
Int32 count = 0;
Int32 length = count;
String subStr = String.Empty;
Boolean searchResult = false;
for (Int32 item = 0; item <= str.Length-1;item++ )
{
searchResult = false;
foreach (Char c in subStr)
{
if (str[item] == c)
{
searchResult = true;
break;
}
}
if (searchResult)
{
subStr = subStr.Substring(1, subStr.Length - 1);
count--;
item--;
}
else
{
subStr += str[item].ToString();
count++;
if (count > length)
{
length = count;
}
}
}
return length;
}
测试代码:
[TestMethod()]
public void GetSubCountTest()
{
SubString target = new SubString(); // TODO: 初始化为适当的值
string str = string.Empty; // TODO: 初始化为适当的值
Assert.AreEqual(0, target.GetSubCount(str));
str = null;
Assert.AreEqual(0, target.GetSubCount(str));
str = "abcbec";
Assert.AreEqual(3, target.GetSubCount(str));
str = "abcd";
Assert.AreEqual(4, target.GetSubCount(str));
str = "a";
Assert.AreEqual(1, target.GetSubCount(str));
str = "aaaaa";
Assert.AreEqual(1, target.GetSubCount(str));
str = "abcdb";
Assert.AreEqual(4, target.GetSubCount(str));
str = "abcdd";
Assert.AreEqual(4, target.GetSubCount(str));
str = "abccc";
Assert.AreEqual(3, target.GetSubCount(str));
str = "aabccc";
Assert.AreEqual(3, target.GetSubCount(str));
}