ສາຍຍາວທີ່ຍາວທີ່ສຸດໂດຍບໍ່ມີຕົວລະຄອນຊ້ ຳ ອີກ  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe ນາມຫລິ້ນກິລາ Amazon ຈາກຫນາກແອບເປີ Bloomberg ByteDance Cisco eBay Expedia ເຟສບຸກ Goldman Sachs ກູໂກ Microsoft Morgan Stanley Oracle SAP ຫ້ອງທົດລອງ SAP Spotify Uber VMware Yahoo
Hash ແຮກ ແຖບເລື່ອນ string ສອງຕົວຊີ້

ມອບໃຫ້ກ string, ພວກເຮົາຕ້ອງຊອກຫາຄວາມຍາວຂອງເສັ້ນຍາວທີ່ຍາວທີ່ສຸດໂດຍບໍ່ຕ້ອງລະບຸຕົວອັກສອນ.

ໃຫ້ເຮົາເບິ່ງຕົວຢ່າງສອງສາມຢ່າງ:

ຍົກຕົວຢ່າງ  

pwwkew
3

ຄຳ ອະທິບາຍ: ຄຳ ຕອບແມ່ນ“ wke” ທີ່ມີຄວາມຍາວ 3

aav
2

ຄຳ ອະທິບາຍ: ຄຳ ຕອບແມ່ນ“ av” ທີ່ມີຄວາມຍາວ 2

ວິທີການ -1 ສຳ ລັບ ສາຍຍາວທີ່ຍາວທີ່ສຸດໂດຍບໍ່ມີຕົວລະຄອນຊ້ ຳ ອີກ   

ຜົນບັງຄັບໃຊ້ສັດ 

ການກວດສອບບັນດາຫົວຂໍ້ຍ່ອຍທັງ ໝົດ ໜຶ່ງ ອັນແມ່ນ ໜຶ່ງ ຕົວອັກສອນທີ່ຊ້ ຳ ກັນ

  • ຄວາມສັບສົນເວລາ
    • ຈຳ ນວນສາຍທີ່ຈະຖືກສ້າງຕັ້ງຂື້ນ = n * (n + 1) / 2
    • ໃຊ້ເວລາໃນການກວດສອບແຕ່ລະສາຍ = O (n)
    • ສະນັ້ນຄວາມສັບສົນເວລາ = O (n ^ 3)
  • ຄວາມສັບສົນໃນອະວະກາດ
    • ການເກັບຮັກສາຕົວອັກສອນທີ່ເກີດຂື້ນ ສຳ ລັບການກວດສອບຄວາມເປັນເອກະລັກ = n
    • ດັ່ງນັ້ນຄວາມສັບສົນໃນອະວະກາດ = O (n)

ວິທີການ -2 ສຳ ລັບ ສາຍຍາວທີ່ຍາວທີ່ສຸດໂດຍບໍ່ມີຕົວລະຄອນຊ້ ຳ ອີກ   

ແຖບເລື່ອນ 

ດຽວນີ້ພວກເຮົາຕິດຕາມ ໜັງ ສື ຄວາມຍາວສູງສຸດ ກັບ ບໍ່ມີຕົວລະຄອນຊ້ ຳ.

  • ໃຫ້ສູງສຸດທີ່ດ
  • ຄວາມຍາວ um ຈະ ສູງສຸດທີ່ເຄຍ ເຊິ່ງເລີ່ມຕົ້ນດ້ວຍ 0
  • ພວກເຮົາຮັບປະກັນວ່າຈາກ  i to j-1 ມີການກວດກາແລ້ວ
  • ທຸກໆຄັ້ງທີ່ພວກເຮົາພົບກັບລັກສະນະ jth
    • ຖ້າ s [j] ບໍ່ຊ້ ຳ
      • ມັນສາມາດຖືກເພີ່ມເຂົ້າໄປໃນທໍ່ຍ່ອຍ
      • ຄວາມຍາວຂອງທໍ່ຍ່ອຍສາມາດເພີ່ມຂື້ນໄດ້
      • j ສາມາດເພີ່ມຂື້ນໄດ້
      • s [j] ສາມາດຖືກບັນທຶກ / ເພີ່ມເຂົ້າໃນ HashSet
    • ຖ້າ s [j] ເຮັດຊ້ ຳ ອີກ
      • ພວກເຮົາເອົາຕົວລະຄອນອອກ
      • ຈຸດເລີ່ມຕົ້ນເຊັ່ນ: ຂ້ອຍ ຈຳ ເປັນຕ້ອງມີການປ່ຽນແປງ
      • ພວກເຮົາເຮັດສິ່ງນີ້ຈົນກ່ວາທໍ່ຍ່ອຍຈະກາຍເປັນການຄ້າງຫ້ອງທີ່ບໍ່ເສຍຄ່າ

ໂຄງການ Java

import java.util.*;
class Solution 
{
    public int lengthOfLongestSubstring(String s)
    {
        int max=0;
        HashSet<Character>hash=new HashSet<Character>();
        int i=0;
        int j=0;
        while(i<s.length() && j<s.length())
        {
            if(hash.contains(s.charAt(j)))
            {
                hash.remove(s.charAt(i));
                i=i+1;
            }
            else
            {
             hash.add(s.charAt(j));
             j=j+1;
             max=Math.max(j-i,max);   
            }
        }
        return max;
    }
}

class Main{
  public static void main(String[] args){
    int answer = (new Solution()).lengthOfLongestSubstring("pwwkew");
    System.out.print(answer);
  }
}
pwwkew
3

ໂຄງການ C ++

class Solution 
{
public:
    int maxs(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int lengthOfLongestSubstring(string s) 
    {
    int max=0;
    set<char>hash;
    int i=0;
    int j=0;
    while(i<s.length() && j<s.length())
    {
      if(hash.count(s[j]))
      {
                hash.erase(s[i]);
                i=i+1;
      }
      else
     {
     hash.insert(s[j]);
     j=j+1;
     max=maxs(j-i,max);   
     }
    }
    return max;    
    }
};
pwwkew
3

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ: O (n)

ເບິ່ງ
ຄົ້ນຫາໃນແຖວທີ່ຖືກຈັດລຽງເປັນແຖວ

ຄວາມສັບສົນໃນອະວະກາດ: O (k) ບ່ອນທີ່ k ແມ່ນຂະ ໜາດ ຂອງປ່ອງຢ້ຽມເລື່ອນລົງ

ວິທີການ -3 ສຳ ລັບ ສາຍຍາວທີ່ຍາວທີ່ສຸດໂດຍບໍ່ມີຕົວລະຄອນຊ້ ຳ ອີກ   

ແຖບເລື່ອນທີ່ດີທີ່ສຸດ 

ໃນວິທີການຂ້າງເທິງ, ພວກເຮົາຮັກສາການ ກຳ ຈັດຕົວອັກສອນແລະປ່ຽນການເລີ່ມຕົ້ນຂອງສາຍຈົນກວ່າພວກເຮົາຈະເຫັນຕົວລະຄອນຊ້ ຳ.

A hashmap ສາມາດຖືກນໍາໃຊ້ເພື່ອຮັກສາການປະກົດຕົວຄັ້ງສຸດທ້າຍຂອງການເຮັດຊ້ໍາອີກຄັ້ງແລະ i (ການເລີ່ມຕົ້ນຂອງທໍ່ຍ່ອຍ) ສາມາດຍ້າຍໄປຫາຈຸດນັ້ນເຮັດໃຫ້ມັນເປັນການດໍາເນີນງານ O (1).

ໂຄງການ Java

import java.util.*;
class Solution 
{
    public int lengthOfLongestSubstring(String s)
    {
        int max=0;
        HashMap<Character,Integer>hash=new HashMap<Character,Integer>();
        int i=0;
        int j=0;
        while(j<s.length())
        {
            if(hash.containsKey(s.charAt(j)))
            {
                i=Math.max(hash.get(s.charAt(j)),i);
            }
             hash.put(s.charAt(j),j+1);
             max=Math.max(j-i+1,max); 
             j=j+1;
        }
        return max;
    }
}

class Main{
  public static void main(String[] args){
    int answer = (new Solution()).lengthOfLongestSubstring("abcdefg");
    System.out.print(answer);
  }
}
abcdefg
7

ໂຄງການ C ++

class Solution 
{
public:
    int maxs(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int lengthOfLongestSubstring(string s) 
    {
    int max=0;
    map<char,int>hash;
    int i=0;
    int j=0;
    while(j<s.length())
    {
    if(hash.count(s[j]))
    {
    i=maxs(hash[s[j]],i);
    }
    hash[s[j]]=j+1;
    max=maxs(j-i+1,max); 
    j=j+1;
    }
    return max;
    }
};
aabbccddee
2

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນທີ່ໃຊ້ເວລາ: O (n)

ຄວາມສັບສົນໃນອະວະກາດ: O (k) ບ່ອນທີ່ k ແມ່ນຂະ ໜາດ ຂອງປ່ອງຢ້ຽມເລື່ອນລົງ

ເອກະສານ