专栏首页流川疯编写程序的艺术leetcode 3 Longest Substring Without Repeating Characters最长无重复子串

leetcode 3 Longest Substring Without Repeating Characters最长无重复子串

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.

这个应该是一个典型的动态规划问题:http://bbs.csdn.net/topics/310174805

直观地得到一个思路,表达起来真够难的,直接写代码要更容易 以abcbef这个串为例 用一个数据结构pos记录每个元素曾出现的下标,初始为-1 从s[0]开始,pos['a'] == -1,说明a还未出现过,令pos['a'] = 0,视为将a"加入当前串",同时长度++ 同理令pos['b'] = 1,pos['c'] = 2 到s[3]时,pos['b'] != -1,说明'b'在前面已经出现过了,此时可得到一个不重复串"abc",刷新当前的最大长度,然后做如下处理: pos[s[0~2]] = -1,亦即将"ab""移出当前串",同时当前长度减去3 重复以上过程

int lengthOfLongestSubstring(string s) {
        vector<int> dict(256, -1);
        int maxLen = 0, start = -1;
        for (int i = 0; i != s.length(); i++) {
            if (dict[s[i]] > start)
                start = dict[s[i]];
            dict[s[i]] = i;
            maxLen = max(maxLen, i - start);
        }
        return maxLen;
    }


/**
 * Solution (DP, O(n)):
 *
 * Assume L[i] = s[m...i], denotes the longest substring without repeating
 * characters that ends up at s[i], and we keep a hashmap for every
 * characters between m ... i, while storing <character, index> in the
 * hashmap.
 * We know that each character will appear only once.
 * Then to find s[i+1]:
 * 1) if s[i+1] does not appear in hashmap
 *    we can just add s[i+1] to hash map. and L[i+1] = s[m...i+1]
 * 2) if s[i+1] exists in hashmap, and the hashmap value (the index) is k
 *    let m = max(m, k), then L[i+1] = s[m...i+1], we also need to update
 *    entry in hashmap to mark the latest occurency of s[i+1].
 *
 * Since we scan the string for only once, and the 'm' will also move from
 * beginning to end for at most once. Overall complexity is O(n).
 *
 * If characters are all in ASCII, we could use array to mimic hashmap.
 */

int lengthOfLongestSubstring(string s) {
    // for ASCII char sequence, use this as a hashmap
    vector<int> charIndex(256, -1);
    int longest = 0, m = 0;

    for (int i = 0; i < s.length(); i++) {
        m = max(charIndex[s[i]] + 1, m);    // automatically takes care of -1 case
        charIndex[s[i]] = i;
        longest = max(longest, i - m + 1);
    }

    return longest;
}

下面给出python代码:

class Solution:
    # @return an integer
    def lengthOfLongestSubstring(self, s):
        start = maxLength = 0
        usedChar = {}

        for i in range(len(s)):
            if s[i] in usedChar and start <= usedChar[s[i]]:
                start = usedChar[s[i]] + 1
            else:
                maxLength = max(maxLength, i - start + 1)

            usedChar[s[i]] = i

        return maxLength

下面是c语言的版本:

// testlongsetString.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>
#include<iostream>

using namespace std;

void GetMaxUnRepeatSubStr(char *str)
{
	//global var
	int hashTable[256] ={0};
	char* pMS = str;
	int mLen = 0;

	//temp var
	char* pStart = pMS;
	int len = mLen;
	char* p = pStart;
	while(*p != '\0')
	{
		if(hashTable[*p] == 1)
		{
			if(len > mLen)
			{
				pMS = pStart;
				mLen = len;
			}

			while(*pStart != *p)
			{
				hashTable[*pStart] = 0;
				pStart++;
				len--;
			}
			pStart++;
		}
		else
		{
			hashTable[*p] = 1;
			len++;
		}
		p++;
	}
	// check the last time
	if(len > mLen)
	{
		pMS = pStart;
		mLen = len;
	}
	//print the longest substring
	while(mLen>0)
	{
		cout<<*pMS<<" ";
		mLen--;
		pMS++;
	}
	cout<<endl;
}

int main()
{
	char* str1="bdabcdcf";
	GetMaxUnRepeatSubStr(str1);
	char* str2="abcdefb";
	GetMaxUnRepeatSubStr(str2);
	char* str3="abcbef";
	GetMaxUnRepeatSubStr(str3);

	return 0;
}

参考文献:

http://bbs.csdn.net/topics/310174805

http://www.cnblogs.com/luxiaoxun/archive/2012/10/02/2710471.html

http://dsqiu.iteye.com/blog/1701324

http://www.ahathinking.com/archives/123.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【编程练习】poj1068

    Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in...

    流川疯
  • leetcode 204题求素数个数

    Count the number of prime numbers less than a non-negative number, n

    流川疯
  • leetcode 5 Longest Palindromic Substring--最长回文字符串

    Given a string S, find the longest palindromic substring in S. You may assume th...

    流川疯
  • 图论--差分约束--POJ 1201 Intervals

    You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn. ...

    风骨散人Chiam
  • 前缀和的应用,从一道网易笔试题说起

    8月3号参加了网易提前批的笔试,笔试时间 120 分钟,然后有 10 道选择题(20分), 4 道编程题(80分), 2 道主观题(20分)。可以说你编程题凉了...

    帅地
  • 写一个程序检查一个整数是2的幂?

    用户4645519
  • C++ Hash表模板

    利用C++类模板实现任意类型的Hash表,提供的功能有: (1)指定shmkey或内存地址创建Hash表; (2)获取指定key元素; (3)遍历指...

    Dabelv
  • C++核心准则ES.106:不要试图通过使用无符号类型避免负值

    Choosing unsigned implies many changes to the usual behavior of integers, includ...

    面向对象思考
  • LeetCode 1390. 四因数

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/four-divisors 著作权归领扣网络所有。商...

    Michael阿明
  • Infinite Fraction Path

    **Infinite Fraction Path** Time Limit: 6000/3000 MS (Java/Others) Memory Limit: ...

    某些人

扫码关注云+社区

领取腾讯云代金券