创新工场涂鸦移动2018校园招聘测试题-软件工程师-编程题二

发表于 | 分类于 ，

题目

描述

给定一字符串只包含数字，请写一个算法，
找出该字符串中的最长不重复子串
（不重复是指子串中每一元素不同于子串中其他元素）

输入

1 行,一个字符全为数字的字符串

输出

1 行,最长不重复子串

Example

Input

120135435

Output

201354

题解

思路

  • 定义 len(i) 为以下标 i 开始的不重复子串的最大长度
  • 初始化 len(i) 为与str[i]相同的下一个字符的距离,若没有则设定下个相同字符的位置为 n
  • 状态转移方程:
1
len(i)=min(len(i),len(i+1)+1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>

using namespace std;
//最长不重复子串
void lookUp(string str)
{
    //获取串长度
    int n=str.length(); 
    //申请辅助空间,flag[i] 为后一个 i 在 str 中的位置,
	//len[i] 为以 i 为第一个字符的不重复子串的长度
    int flag[10],*len=new int[n+5]; 
    //初始化 flag
    for(int i=0;i<10;++i)   
        flag[i]=n;
    //初始化 len
    memset(len,0,sizeof len);   
    len[n]=0;
    //初始化 len[i] 为当前字符与其后面第一个相同的自字符的距离
    for(int i=n-1;i>=0;--i) 
    {
        len[i]=flag[str[i]-'0']-i;
        flag[str[i]-'0']=i;
    }
    //保存最大子串的首
    int maxi=n; 
    for(int i=n-1;i>=0;--i)
    {
        //len[i] 的值更新为 len[i] 与 len[i+1]+1 两数之中的小者
        len[i]=min(len[i],len[i+1]+1); 
        //更新最长不重复子串首字符位置 
        if(len[maxi]<len[i])maxi=i; 
    }
    //输出最长不重复子串
    for(int i=maxi;i-maxi<len[maxi];++i)    
        printf("%c",str[i]);
}
//测试
int main()
{
    string str;
    while(cin>>str)
    {
        lookUp(str);
    }
}