Length of the strings

dangth · May 22, 2015, 4:29am

Hiện tại mình đang có 1 bài toán như sau:

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Hướng giải quyết bài này của mình là:

Giả sử có 1 chuỗi a0…aN, ta so sánh bắt đầu từ a0.

Nếu a0 != a1 thì ta sẽ cho a0a1 thành 1 nhóm sau đó xét tiếp tục vs a2, nếu a0a1 != a2 thì tiếp tục xét nhóm a0a1a2 vs a3,…aN.
Nếu trong quá trình chạy, xuất hiện a[i] == a[j] thì sẽ xuất ra chuỗi a0…ai và lại tiếp tục xét từ a[i+1] cho đến hết.

ví dụ:

Có chuỗi

1 2 2 1 4 3 1 5 6 2 1 2 4 5 8

a1 != a2
a2 == a3
-> a1 a2 = 1 2
tiếp tục từ a3
a3 != a4
a4 != a5
a5 != a6
a6 != a7 and a4 == a7
-> a3 a4 a5 a6 = 2 1 4 3
tiếp tục từ a5
a5 != a6
a6 != a7
a7 != a8
a8 != a9
a9 != 1a10
a10 != a11 and a7 == a11
-> a5-6-7-8-9-10 = 4 3 1 5 6 2
tiếp tục từ a8
a8 != a9
a9 != 1a10
a10 != a11
a10 != a11
a11 != a12 and a10 == a12
-> a8-9-10-11 = 5 6 2 1
tiếp tục từ a11
a11 != a12
a12 != a13
a13 != a14
a14 != a15
->a11-12-13-14-15 = 1 2 4 5 8
chuỗi có độ dài nhất là a5-6-7-8-9-10 , length = 6

Ý tưởng là vậy nhưng hiên tại vẫn chưa biết viết thuật giải và code ra sao cả, mong ae có ý kiến thông não. mình là newbie

thanhmssl10 · May 22, 2015, 3:57am

Mình copy nguyên cái đề của bạn cho anh google nó được thế này

http://articles.leetcode.com/2011/05/longest-substring-without-repeating-characters.html
http://maogm.com/blog/longest-substring-without-repeating-characters-en.html
https://www.google.com/search?q=Given+a+string%2C+find+the+length+of+the+longest+substring+without+repeating+characters.+For+example%2C+the+longest+substring+without+repeating+letters+fo&ie=utf-8&oe=utf-8

nitneiht · May 22, 2015, 4:27am

mình implement theo ý tưởng của bạn sử dụng python

myList = []
result = []
aString = "abcabcabcd"
for i in aString:
    if(i not in myList):
        myList.append(i)
    else:
        result.append(len(myList))
        print myList
        myList = []
        myList.append(i)

print max(result)

trường hợp chuỗi con dài nhất nằm ở cuối chuỗi ban đầu thì nó ko xuất ra đúng kết quả bạn xem tự sửa trường hợp đó

dangth · May 22, 2015, 5:12am

thanks bác , cái naỳ e copy paste ngay từ khi nhận đc đề bài

dangth · May 22, 2015, 5:15am

e vừa check thì đúng là ko đúng thật, vẫn bị xét thiếu trường hợp bác ạ, nhưng vẫn phải cảm ơn bác vì phát thông não tê người

nitneiht · May 22, 2015, 5:35am

Cái version 0.1 mình quên chỉ xét chuỗi con rồi bỏ chuỗi đó ra khỏi chuỗi ban đầu mà đáng ra phải xét chuỗi con từ kí tự kế tiếp. hihi .

dangth · May 22, 2015, 8:17am

học dốt thật, e check các kiểu cho chạy thêm 1 vòng for, gán i thêm 1 lần +1 mà vẫn ko xét đc cái kí tự kế tiếp

nitneiht · May 24, 2015, 3:26am

Ý tưởng là bắt đầu từ kí tự đầu tiên tìm chuỗi con cho tới khi gặp kí tự trùng lặp dừng lại ko duyệt tới hết chuỗi ban đầu. Process tới kí tự kế tiếp cho đến cuối hoặc có thể dừng khi độ dài chuỗi phải xét < max value của result. Bạn xem mấy cái output là hiểu ngay. ko biết format code sao nhỉ.

result = []
aString = "122143156212458"
def stringlen(aStr):
    myList = []
    for i in aStr:
        if(i not in myList):
            myList.append(i)
        else:
            result.append(len(myList))
            #print myList
            #myList = []
            #myList.append(i)
            break
        result.append(len(myList))
        print myList
while len(aString) > 0:
    stringlen(aString)
    aString = aString[1:]
    print aString
print max(result)