Longest Substring Without Repeating Characters

发布时间:2017-6-29 10:47:57编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Longest Substring Without Repeating Characters",主要涉及到Longest Substring Without Repeating Characters方面的内容,对于Longest Substring Without Repeating Characters感兴趣的同学可以参考一下。

问题

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

解题思想

存在子串 xi,xi+1,...,xj1互异,现在第xj个字符
xjxi,xi+1,...,xj1互异,则j=j+1, 否则存在k使得xk==xj,这时我们只需要算出此区间最大的长度ji+1, 并将i移动到i=k+1, 此时区间长度为jk.

代码

// 找到c在s[from, end]中的位置
int find(char *s, int from, int end, char c) {
    int i;
    for (i = from; i <= end; ++i) {
        if (s[i] == c) {
            return i;
        }
    }
    return -1;
}

int lengthOfLongestSubstring(char* s) {
    int length_s = strlen(s);
    if (length_s < 2) {
        return length_s;
    }
    int longest = 1;
    int tmp_count = 1;
    int i, j;
    int k;

    for (i = 0, j = 1; j < length_s; ++j) {
        k = find(s, i, j - 1, s[j]);
        if (k == -1) {
            tmp_count++;
            continue;
        } else {
            if (tmp_count > longest) {
                longest = tmp_count;
            }
            i = k + 1;
            tmp_count = j - i + 1;
        }
    }
    if (tmp_count > longest) {
        longest = tmp_count;
    }
    return longest;
}Characters

性能

这里写图片描述



上一篇:JAVA 重载,返回类型
下一篇:七、顺序队列

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款