Fe-interview: 第 4 题：字符串出现的不重复最长长度

[lgwebdream]

欢迎在下方发表您的优质见解

[Genzhen]

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    const arr = [...s]
    let res = 1;
    let result = arr.reduce((total, cur, i, arr) => {
        if (i == 0) {
            return cur;
        } else {
            if (total.indexOf(cur) < 0) {
                return total + cur
            } else if (res < total.length) {
                res = total.length
                return total.slice(total.indexOf(cur) + 1, total.length) + cur
            } else {
                return total.slice(total.indexOf(cur) + 1, total.length) + cur
            }
        }
    }, "")
    if (res < result.length) {
        res = result.length
    }

    return res
};

console.log(lengthOfLongestSubstring("loddktdji"))
console.log(lengthOfLongestSubstring("dvdf"))
console.log(lengthOfLongestSubstring("adfafwefffdasdcx"))

[Genzhen]

/**
 * 题目：字符串出现的不重复最长长度
 * 整体思路：
 * 用一个滑动窗口装没有重复的字符，枚举字符记录最大值即可
 * 对于遇到重复字符如何收缩窗口大小？
 * 我们可以用 map 维护字符的索引，遇到相同的字符，把左边界移动过去即可
 * 挪动的过程中记录最大长度
 */
var lengthOfLongestSubstring = function (s) {
    let map = new Map();
    let i = -1
    let res = 0
    let n = s.length
    for (let j = 0; j < n; j++) {
        if (map.has(s[j])) {
            i = Math.max(i, map.get(s[j]))
        }
        res = Math.max(res, j - i)
        map.set(s[j], j)
    }
    return res
};

[wangyingjie123]

function lengthOfLongestSubstring(s) {
   let max = 0;
   let arr = [];
  for (let i = 0; i < s.length; i++) {
   let index = arr.indexOf(s[i]);
   if (index !== -1) {
      arr.slice(0, index + 1);
  }
  arr.push(s[i]);
  max = Math.max(max, arr.length);
}
return max;
}

[123456zzz]

const lengthOfLongestSubString = (s: string) => {
  let left = 0,
    right = 0,
    res = 0,
    map = new Map();
  while (right < s.length) {
    if (map.has(s[right])) {
      left = Math.max(left, right);
    }
    res = Math.max(res, right - left + 1);
    map.set(s[right], right);
    right++;
  }
  return res;
};

console.assert(lengthOfLongestSubString("") === 0);

console.assert(lengthOfLongestSubString("aa") === 1);

console.assert(lengthOfLongestSubString("aabc") === 3);

[chengming9731]

function lenSetStr (str) {
    return [...new Set(str)].length
}

不会调整格式凑合看

[jzsn2018]

function lenSetStr (str) {
    return [...new Set(str)].length
}

不会调整格式凑合看

不是这样吧

[cool-518]

麻烦把题目表述清楚行吗？装什么呢，中文没学好？

[cool-518]

@wangyingjie123 楼上的，写的对不对自己没数吗？能不能自己充分验证了再发出来？

[pioneer22]

function lengthOfStr (str) {
  let res = ""
  let result = [...str].reduce((acc, v, i) => {
    if (i === 0) {
      return v;
    } else {
      if (acc.indexOf(v) < 0) {
        return acc + v
      } else {
        res = res.length < acc.length ? acc : res
        return acc.slice(acc.indexOf(v) + 1, acc.length) + v
      }
    }
  }, "")
  console.log(res.length > result.length ? res : result)
  return Math.max(res.length, result.length)
}

[Snailmar]

```js
function lenSetStr (str) {
    return [...new Set(str)].length
}

不会调整格式凑合看
```

你这何止是不会调格式，你这是不会读题啊！

[yangbibo]

var str = 'abacvdtrgasgdoijmiqunvlhsdanwqp';
var longStr = (str) => {
var long = 0;
var arr = []
for(var i=0;(i+long) var index = arr.indexOf(str[i]);
arr.push(str[i]);
if(index!==-1){
arr.splice(0,index+1)
}
long = Math.max(arr.length,long)
}
return long
}
longStr(str)

[cody1991]

/*
 * @Author: codytang
 * @Date: 2020-07-18 17:54:20
 * @LastEditTime: 2020-07-18 18:01:55
 * @LastEditors: codytang
 * @Description: 第 4 题：字符串出现的不重复最长长度
 */

function longNoRepeatStr(str) {
  let max = -Infinity;
  let count = 0;
  let pre = null;

  for (let index = 0; index < str.length; index += 1) {
    const cur = str[index];

    if (cur !== pre) {
      count += 1;
    } else {
      count = 1;
    }

    pre = cur;
    if (count > max) max = count;
  }
  return max;
}

console.log(longNoRepeatStr("aabccddabcde"));  //6

[GolderBrother]

var lengthOfLongestSubstring = function (s = '') {
let map = new Map();
let i = -1,
res = 0,
len = s.length;
for(let j = 0; j < len; j++) {
if(map.has(s[j])) {
// 遇到重复项，记录索引值
i = Math.max(i, map.get(s[j]))
}
// 更新最大长度，减掉重复项索引
res = Math.max(res, j - i);
map.set(s[j], j);
}
}

[Kelier]

var maxLen = function(s){
    let max = 0;
    let str = '';
    for(let i=0;i<s.length;i++){
        if(str.indexOf(s[i]) < 0) {
            str += s[i];
            if(str.length>max){
                max = str.length;
            }
        } else {
            str = str.slice(str.indexOf(s[i])+1) + s[i];
        }
    }
    return max;
}

[Z6T]

遍历的同时,进行截取比较

let str = 'fdsfsdzffdfdddfsdsds'

let arr = []
const s = str.split('')
let total= 0; // 长度
let maxStr = '' // 最长不重复长度的字符串
for(var i = 0;i <s.length;i++){
    const ele = s[i]
    const idx = arr.indexOf(ele)
    if(idx>-1){
        arr = arr.slice(idx+1)
    }
    arr.push(ele)
    if(arr.length>total){
        maxStr = arr.join('')
        total = arr.length
    }
}

console.log(total)
console.log(maxStr)

[pangyongsheng]

const twoSum = function(nums, target) {
let a, b;
for(let i = 0; i < nums.length; i++) {
let tmp = target - nums[i];
let arr = nums.slice(i+1);
let ind = arr.indexOf(tmp);
if(ind > -1){
a = i;
b = i + 1 + ind;
break;
}
}
return [a, b];
};

[chun1hao]

function fn(s) {
    let temps = '',max=0
    for(let i=0;i<s.length;i++){
        let current = s[i]
        if(temps.indexOf(s[i]) !== -1){
            temps = temps.substring(temps.indexOf(s[i])+1)            
        }
        temps += current
        max = Math.max(temps.length, max)
    }
    return max
}

[xcgs123]

function maxLength(str) {
    let res = []
    let arr = str.split('')
    let max=0
    while (arr.length>0) {
        let cur = arr.shift()
        if(!res.includes(cur)){
            res.push(cur)
        }else{
            max=Math.max(max, res.length)
            res = []
        }
    }
    console.log(max)
}
maxLength('112345123')

[Hasky0911]

function longNoRepeatStr(str) {
      if (Object.prototype.toString.call(str) !== '[object String]') throw 'unvalid string'
      let arr = str.split('')
      return Array.from(new Set(arr)).length
}
console.log(longNoRepeatStr('ssdfsd'))

[MiRinZhang]

/**
 * @param str {string}
 * 使用快慢双指针；对比快慢指针所指的值，如果不相等则计数加1，否则计数重置
 */
function maxNoRepeatStr (str) {
    // 为空时，直接返回0
    if (!str) {
        return 0;
    }

    // 慢指针指向0
    let slow = 0;
    // 快指针指向1
    let fast = 1;
    // 计数默认为1 - 至少一个不重复
    let count = 1;

    // 当快指针走到结尾时停止
    while (str.length > fast) {
        // 不相等，计数加1
        if (str[slow] !== str[fast]) {
            count++;
        } else {
            // 重置为1
            count = 1;
        }
        // 快慢指针同时走
        slow++;
        fast++;
    }

    return count;
}

console.assert(maxNoRepeatStr("loddktdji") === 6);
console.assert(maxNoRepeatStr("dvdf") === 4);
console.assert(maxNoRepeatStr("adfafwefffdasdcx") === 7);

[GitHubzwd]

function strNorepeatMaxLength (str) {
let repeatIndex = 0,
maxLength = 0;;
for (let i = 0; i < str.length; i++) {
if (i > 0 && (str[i] === str[i - 1])) {
if (i - repeatIndex > maxLength) {
maxLength = i - repeatIndex;
}
repeatIndex = i;
}
}
return maxLength === 0 ? str.length : (str.length - repeatIndex > maxLength ? str.length - repeatIndex : maxLength);
}
strNorepeatMaxLength("1234555123456") // 输出7

[huzedong2015]

const str = "efdfabcdefghiabbcccdef";
const len = str.length;
let maxStr = "";

// 获取所有可能
for (let i = 0; i < len; i++) {
    let temp = "";

    for (let j = i; j < len; j++) {

        if (!temp.includes(str[j])) {
            temp += str[j];
        } else {
            break;
        }
    }

    if (temp.length > maxStr.length) {
        maxStr = temp;
    }
}

console.log(maxStr);

[webzsp]

str.length?

[RainyNight9]

function maxStrLen(str) {
    if (!str) return 0;
    let arr = str.split('')
    let max = 0
    for (i = 0; i < str.length; i++) {
        arr[i] = 'pass'
        let index = arr.indexOf(str[i])
        if (index !== -1 && index - i > max) max = index - i
    }
    return max
}
maxStrLen('pwwkew')
maxStrLen('abcabcbb')
maxStrLen('bbbbb')
maxStrLen('123456125')
maxStrLen('123 45 6125')
maxStrLen('')

[carbrokers]

/**
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstring (str) {
  if (str.length === 0 || str.length === 1) {
    return str.length;
  }

  let start = 0;
  let end = 0;
  let maxStr = str[0];
  let location = {
    [str[0]]: 0
  }
  for (let index = 1; index < str.length; index++) {
    const char = str[index];
    if (typeof location[char] !== 'undefined') {
        if (location[char] >= start) { 
            start = location[char] + 1;
        }
    }
    location[char] = index;
    end++;

    if ((end - start + 1) > maxStr.length) {
      maxStr = str.substring(start, end + 1);
    }
  }
  return maxStr.length;
}

[jesse-li]

function str(str) {
                if (typeof str !== 'string') return 0;
                let strArr = [...str];
                let prev = '';
                let curr = '';
                let length = 1;
                let max = 1;
                for (let i = 0; i < strArr.length - 1; i++) {
                    prev = strArr[i];
                    curr = strArr[i + 1];
                    if (prev !== curr) {
                        length++;
                    } else {
                        max = Math.max(max, length);
                        length = 1;
                    }
                }
                return Math.max(max, length);
            }

说下思路，每个字符比较，如果有相同就保存当前length，没有就++，最后对比。

[467057463]

这题目没看懂

[noney]

```javascript
/**

• [noRepeaMaxLenStr description]
• @param {String} str [字符串]
• @return {[type]} [description]
  */
  function noRepeaMaxLenStr(str = '') {
  let arr = [...str],
  start = end = arr.shift(),
  resArr = [],
  len = 0;
  str = '';
  for (let v of arr) {
  if (v === start) {
  resArr.push(end);
  start = end = v;
  } else {
  start = v;
  end+= v;
  }
  }
  resArr.push(end);
  console.log(resArr);
  for(let v of resArr) {
  if (len < v.length) {
  len = v.length;
  str = v;
  }
  }
  console.log({len, str})
  return {len, str};
  }

noRepeaMaxLenStr('abbcdeefg');
noRepeaMaxLenStr('aaabcdeeeff');
noRepeaMaxLenStr('abccdeffgg');

[Patrick9527]

const longestLength = (string) => {
    const length = string.length;
    const recordArr = [];
    for(let i = 0; i < length; i++) {
        const arr = string.split('');
        const emptyArr = [];
        for(let j = 0; j < length - i; j++) {
            emptyArr.push(arr[i + j]);
            const newSetArr = [...new Set(emptyArr)];
            if(newSetArr.length !== emptyArr.length) {
                recordArr.push(newSetArr.length)
                break;
            } else if(j === length - i - 1) {
                recordArr.push(newSetArr.length)
            }
        }
    }
    return Math.max.apply(null, recordArr);
}

console.log('this is',longestLength('1lksdmfkdfasdfasdf20393'));

[linbaichuan0818]

function maxNoRepeatStr(str){
  if(typeof str !== 'string') return console.warn("Expected string, But got " +  typeof str);
  let noRepeatStr = '';
  let lastIndex = str.length - 1;
  let max = 0;

  do {
     const last = str[lastIndex], next = str[lastIndex-1];
     last === next?
     noRepeatStr = '':
     noRepeatStr += last;
     max = Math.max(max, noRepeatStr.length + 1);
  } while (--lastIndex);

  return max;
}
console.assert(maxNoRepeatStr("loddktdji") === 6);
console.assert(maxNoRepeatStr("dvdf") === 4);
console.assert(maxNoRepeatStr("adfafwefffdasdcx") === 8);

[markduan]

不推荐，时间和空间复杂度都太高。

let n = 0;

function getSubStrings(str, length) {
  const subStrings = [];
  for(let i = 0; i + length <= str.length; i++) {
    n = n + 1;
    subStrings.push(str.slice(i, i + length));
  }

  return subStrings;
}

function longestSubString(str, length) {
  const noRepeating = getSubStrings(str, length).some((str) => {
    n = n + 1;
    const flag = new Set(str.split('')).size === length;
    if (flag) {
      console.log('find longest without repeating sub string:', str);
      return true;
    }

    return false;
  });

  if (noRepeating) {
    return length;
  }

  return longestSubString(str, length - 1);
}

console.log('the length is:', longestSubString('ABDEFGABEF', 'ABDEFGABEF'.length));
console.log('loop count:', n);

[jeckAell]

/*8 
* 思路：1.使用动态创建对象的方式，将每个字符当作对象的属性名。在设置一个属性名之前，看看能否取到该属性名的值，
  *         如果没有则设置属性为该字符，且赋值为1。如果一旦取到了就说明已经设置过该属性，直接得到长度
  */

  const getLongestStrLength = (s) => {
      let obj = {}

      for (let i = 0; i < s.length; i ++) {
        if (obj[s[i]] === 1) {
            return i
          } else {
            obj[s[i]] = 1  
          }
      }

      return '没有'
  }

[gitwujiaolong]

let str='11abcdef1e111aabbcef'
let lengthTag = 1
let maxLengthArr = []
for(let i=1;i if(str[i]!==str[i-1]){
lengthTag++;
}else{
maxLengthArr.push(lengthTag)
lengthTag = 1;
}
}
console.log(Math.max(...maxLengthArr)) // 10

[Jean1024]

var str = 'Lorem,ipsumdolorsitametconsectetura'
const getUniqueIndex = function (str) {
  var obj = {}
  for (const key in str) {
    var letter = str[key]
    if (obj[letter]) return key
    obj[letter] = 1
  }
  return str.length
}
var index = getUniqueIndex(str)
console.log(index)

[1045922393]

function longNoRepeatLongth(str: string): number {
let max = 0;
for (let i = 0; i < str.length; i++) {
let strTemp = ''
for (let j = i; j < str.length; j++) {
if (strTemp.includes(str[j])) {
break;
} else {
strTemp += str[j]
}
}
max = strTemp.length >= max ? strTemp.length : max;
}
return max;
}

function longNoRepeatLongth2(str: string): number {
let temp = '';
let arr = str
let max = 0;
for (let i = 0; i < arr.length; i++) {
if (!temp.includes(arr[i])) {
temp += arr[i]
} else {
max = temp.length >= max ? temp.length : max;
temp = arr[i];
}
}
max = temp.length >= max ? temp.length : max;
return max;
}

[baixc1]

// 第 4 题：字符串出现的不重复最长长度
function lengthOfLongestSubstring(s) {
  let max = 0; // 最长长度
  let dict = {}; // 纪录当前字符串的下标位置
  let i = 0; // 遍历 字符串s 的指针
  let cur = 0; // 当前无重复字符串的指针
  while (i < s.length) {
    if (!dict[s[i]]) {
      dict[s[i]] = String(i); // 再次遍历, i 在 字符串s 的位置
      i++;
      cur++;
    } else {
      i = dict[s[i]] + 1;
      cur = 0;
      dict = {};
    }
    if (cur > max) {
      max = cur;
    }
  }
  return max;
}
console.log(lengthOfLongestSubstring("loddktdji"));
console.log(lengthOfLongestSubstring("dvdf"));
console.log(lengthOfLongestSubstring("adfafwefffdasdcx"));

[papillon328]

const getLongestStrLen = (s) => {
    const len = s.length; 
    let str = '';
    let res = 0;
    let char, index;
    for(let i=0; i<len; i++){
        char = s.charAt(i);
        index = str.indexOf(char);
        if(index === -1){
            str += char;
            res = res < str.length ? str.length : res;
        } else{
            str = str.substr(index + 1) + char;
        }
    }

    return res;
}

[wulaoge]

滑动窗口

var lengthOfLongestSubstring = function(s) {
    let len = s.length
    let left = 0 //窗口左指针
    let right = 0 //窗口右指针
    let map = {} //无重复字符串的map
    let maxLen = 0 
    while(right < len){
        //遇到重复字符串左指针左移缩小窗口
        while(map[s[right]]){
            delete map[s[left]]
            left++
        }
        // 右指针右移扩大窗口，并记录数据到无重复的map里
        map[s[right]] = 1
        right++

        maxLen = Math.max(maxLen,right - left)
    }
    return maxLen
}

[webyangpei]

/**
 * @param str {string}
 * 使用快慢双指针；对比快慢指针所指的值，如果不相等则计数加1，否则计数重置
 */
function maxNoRepeatStr (str) {
  // 为空时，直接返回0
    if (!str) {
        return 0;
    }

  // 慢指针指向0
    let slow = 0;
  // 快指针指向1
    let fast = 1;
  // 计数默认为1 - 至少一个不重复
    let count = 1;

  // 当快指针走到结尾时停止
    while (str.length > fast) {
      // 不相等，计数加1
        if (str[slow] !== str[fast]) {
            count++;
        } else {
          // 重置为1
            count = 1;
        }
      // 快慢指针同时走
        slow++;
        fast++;
    }

    return count;
}

console.assert(maxNoRepeatStr("loddktdji") === 6);
console.assert(maxNoRepeatStr("dvdf") === 4);
console.assert(maxNoRepeatStr("adfafwefffdasdcx") === 7);

console.assert(maxNoRepeatStr("asyncDataloddktdji") === 6); // true

[tangchuanxi]

function lenSetStr (str) {
    return [...new Set(str)].length
}

不会调整格式凑合看

审题不对

[tangchuanxi]

// 'a'
let str = 'sfdjlnmvsfdskljflskfbsfdsslkdkkk'

// 判重
function hasRepeat(str) {
let str1 = Array.from(new Set(str))
return str1.length !== str.length
}
function findMaxDiffSub(allStr) {
let maxArr = []
for (let sliceLength = 0, len = allStr.length; sliceLength < len; sliceLength++) {
// sliceLength 切割长度
for(let index=0; index < allStr.length - sliceLength; index++){
let subStr = allStr.slice(index, index+sliceLength)
if(!hasRepeat(subStr)) {
maxArr = subStr;
}
}
}

console.log('max length is', maxArr.length)
console.log('max arr is', maxArr)

}

findMaxDiffSub(str)

[tangchuanxi]

// 快慢指针
// 判重
function hasRepeat(str) {
let str1 = Array.from(new Set(str));
return str1.length !== str.length;
}

function maxNoRepeatStr(str) {
let slow = 0; // 慢指针
let fast = 1; // 快指针
let maxStr = '';
let subStr = '';

// 扫描整个字符串
while (fast <= str.length) {
subStr = str.substring(slow, fast);
// 是否重复？
if (!hasRepeat(subStr)) {
if (subStr.length > maxStr.length) {
maxStr = subStr;
}
fast++;
} else {
// 有重复
slow++;
}
}
console.log(max norepeat string is ${maxStr}, length is ${maxStr.length});
}

// test
const testStr = 'sfdjlnmvsfdskljflskfbsfdsslkdkkk';
const testStr1 = '121';
const testStr2 = '1';
console.log(maxNoRepeatStr(testStr));
console.log(maxNoRepeatStr(testStr1));
console.log(maxNoRepeatStr(testStr2));

[Jam-Chu]

滑动窗

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    let
        finalLength = 0,
        tempLength = 0,
        // window的结构为key（字母表示）:value（字母下标）
        window = {},
        left = 0,
        right = 0;
    while (left < s.length && right < s.length) {
        // 如果记录表中没有，或记录的位置不在滑动窗口内，则继续扩张
        if (window[s[right]] === undefined || window[s[right]] < left) {
            window[s[right]] = right;
            tempLength = right - left + 1;
            finalLength = finalLength >= tempLength ? finalLength : tempLength;
        } 
        // 否则，收缩窗口至重复的下一个
        else {
            left = window[s[right]] + 1;
            window[s[right]] = right;
            tempLength = right - left + 1;
        }
        right++;
    }
    return finalLength;
};

[wangtg1]

function strLen(str) {
if(typeof str !== 'string') {
throw TypeError(str + 'is not a string')
}
// 如果长度小于等于一 直接返回
if(str.length < 2) return str.length;
const strArr = str.split('')
// 数组去重
const newArr = Array.from(new Set(strArr))

return newArr.length;

}

[BrucelLi]

const noRepeatStrLen = (s) => {
    let tmpStr = '';
    for (let i = 0; i < s.length; i++) {
      if (tmpStr.indexOf(s[i]) === -1) {
        tmpStr += s[i];
      } else {
        return tmpStr;
      }
    }
    return tmpStr;
  }

  console.log(noRepeatStrLen('abcabc'));
  console.log(noRepeatStrLen('abcd123'));
  console.log(noRepeatStrLen('aa24'));

[kaden1989]

题目竟然没读懂。。。

[qzruncode]

function deStr(str) {
  let tmpStr = '';
  let maxStr = '';
  for(let i = 0; i < str.length; i++) {
    const index = tmpStr.indexOf(str[i]);
    if(index != -1) { // 原来的不重复字符串，找到重复的字符
      if(maxStr.length <= tmpStr.length) {
        maxStr = tmpStr;
      }
      tmpStr += str[i];
      tmpStr = tmpStr.slice(index + 1);
    }else {
      tmpStr += str[i];
    }
  }
  return maxStr ? maxStr : str;
}
deStr('abacbefkb')

[laihaoshan]

function strLength (str) {
  let index = 1
  let stack = ''
  let maxStr = 0
  let same = 0
  while (index <= str.length) {
    let text = str.substring(index, 0)
    if(stack.substr(stack.length - 1, 1) === text.substr(text.length - 1, 1)) {
      same = text.length - 1
      if(stack.length > maxStr) {
        maxStr = stack.length
      }
    } else {
      stack = text.substring(same)
    }
    index ++
  }
  return stack.length > maxStr ? stack.length : maxStr
}

把自己的拿上来，看看跟大佬的差距有多少