我有个有趣的任务。 我需要从字符串中获取最大的唯一字符部分。
例如:
（不唯一，唯一字符的最大部分）
我用这个解决方案解决了任务。
let str = 'ertyukembvcx'
let part = ''
let maxpart = ''
for( let i = 0 ; i<str.length; i++ ) {
for( let j = i + 1 ; j<str.length ; j++) {
if(!str.slice(i,j).includes(str[j])){
part = str.slice(i,j+1)
if(maxpart.length< part.length)
maxpart = part
}
else{
break
}
}
}
console.log(maxpart)
也许有人有更好的解决办法？
您的算法以二次时间复杂度运行。 你可以从这个观察中看到它可以变得更有效率:
假设您发现在内循环中字符仍然是唯一的，i==0和j==5。 下一次迭代外部循环并使i=1时，遗憾的是您将时间花费在j=2，j=3，j=4，j=5上，因为从i仍然为0时起，您就已经知道这些具有i==1的子字符串没有重复项。 如果slice(0，6)没有重复字符，那么slice(1，6)当然也没有重复字符。
您可以使用映射或对象来记录您当前正在迭代的字符的最近的字符位置。 如果这比您考虑的子字符串的当前起始位置更靠右，那么您必须将该切片的起始位置移到该索引之外，从而使子字符串更短。 保持跟踪最长的子字符串是什么，你得到的方式。
这里是算法。 这以线性时间复杂度运行:
null
function uniqueSubstring(str) {
let charMap = Object.fromEntries(Array.from(str, c => [c, -1]));
let left = 0;
let best = 0;
let bestLeft = 0;
for (let right = 0; right < str.length; right++) {
let prev = charMap[str[right]];
charMap[str[right]] = right;
if (prev >= left) {
left = prev + 1;
} else if (best < right - left) {
best = right - left;
bestLeft = left;
}
}
return str.slice(bestLeft, bestLeft+best+1);
}
let tests = [
['qwebwerty', 'bwerty'],
['ertyukembvcx', 'rtyukembvcx'],
['worldhello', 'worldhe'],
['gvhbbrother', 'brothe'],
];
for (let [str, expected] of tests) {
let result = uniqueSubstring(str);
console.log(str, result);
if (result != expected) console.log(" ... but expected: " + expected);
}