问题:
找到一个字符串中的一个连续子串,这个子串内不能有任何两个字符是相同的,并且这个子串是符合要求的最长的。
程序:
代码
/************************************************************************/
/* 求最长不重复子串 */
/************************************************************************/
void lnorepstr(char* s)
{
char A[26];
int i, j;
int maxi, maxlen = 0;
int len = strlen(s);
// for(i = 0; i < 26; i++)
// A[i] = -1;
memset(A, -1, 26);
for (i = 0; i < len; i++)
{
A[s[i] - 'a'] = 1;
for(j = i+1 ; j < len; j++)
{
if(A[s[j]-'a'] == -1) //该字符没有出现
{
A[s[j]-'a'] = 1;
if(j - i> maxlen)
{
maxlen = j - i;
maxi = i;
}
}
else
break;
}
memset(A, -1, 26);
}
printf("longest no repeat string: %.*s\n", maxlen+1, &s[maxi]);
}
假设字符串全部是由小写字母组成,则内层循环最多执行26次,即最长不重复子串的长度为26,此时,时间复杂度为O(26n)。
分享到:
相关推荐
寻找最长不重复子串 python代码
本文实例讲述了Python简单实现查找一个字符串中最长不重复子串的方法。分享给大家供大家参考,具体如下: 刚结束的一个笔试题,很简单,不多说简单贴一下具体的实现: #!usr/bin/env python #encoding:utf-8 ''''' ...
主要介绍了Python实现针对给定字符串寻找最长非重复子串的方法,涉及Python针对字符串的遍历、排序、计算等相关操作技巧,需要的朋友可以参考下
最长不重复子串及最长回文子串 \n"); printf(" 4.每个字符出现概率 \n"); printf(" 5.生成哈夫曼树并进行编码 \n"); printf(" 6.将文本转化为代码文件 \n"); printf(" 7.把二进制码解码成明文并与原函数对比 ...
Scratch不重复子串 第十五届蓝桥杯Scratch编程选拔赛真题源码 考点:此案例难度系数4;综合考查角色、背景添加、坐标、循环、条件判断、侦测模块、按下鼠标事件、询问机制、关系运算、列表操作、自定义积木等相关...
通过C++方法实现串中最大重复子串 初始设子串起始位置index=0,最长重复子串...再从s_(i+length1)之后找重复子串,然后对于s_(i+1)之后的字符采用相同的方法,最后的index与length即记录下最长重复子串的下表与长度。
在字符串中找到最长的不包含重复字符的子串,返回其长度
# 给定一个字符串,找出不含有重复字符的最长子串的长度 # 示例 1: # 输入: "abcabcbb" # 输出: 3 # 解释: 无重复字符的最长子串是 "abc",其长度为 3 # 示例 2: # 输入: "bbbbb" # 输出: 1 # 解释: 无重复字符的...
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例: 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 ...
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters 一上来没啥思路,好久不做题...
leetcode数组下标大于间距 ...最长不重复子串(获取长度) 使用一个可截取的字符串,或者队列(FIFO)来遍历一遍原字符串,当有字母重复的时候,开始从头删,一直到删除重复的元素,然后继续遍历,最后O(n)得到max
js代码-(算法)(字符串)找最大不重复子串
题解 1: 维持一个滑动窗口来做比较,初始时...字符不存在则存在 map 中。 耗时 0 ms package main import ( fmt strings ) func main() { s := abcabcbb fmt.Println(getLongStr(s)) } func getLongStr(s stri
最长不重复子串 (medium) 大中小括号是否合规 (easy) 字符串集合的最长公共prefix (easy) Day2 判断数字是否是回文 (easy) 翻转数字 (easy) 罗马数字(easy) Day3 两个有序的链表合并成一个有序链表 (easy)...
最长不重复子串问题 Date : 2018-09-07 Q4 两个有序数组中位数问题 利用递归减少问题规模 较难 花了较长的时间来解决该题 Date : 2018-09-07 Q5 最长回文子串问题 利用了DP的思想 Date : 2018-09-10 Q6 按一定规则...
1.无重复字符的最长子串滑动窗口, 也是基于left指针和right指针的算法。一直往右移动,如果下一个值在本字符串中有,left+=index+1相当于跳过去
查找字符串中的最长不重复子串的长度 4. 手动实现atio函数,转换str到int 5. 判断一个整数是否为回文数,不使用额外变量 6. 合并两棵二叉树 7. 实现.*正则表达式匹配函数 8. 将两个链表整数相加 9. 从数组中寻找和的...
解题步骤:统计每个字符出现的次数找第一个出现次数介于0-k之间字符,这个字符就作为分割点,把s分割为若干个不包含该字符的子串用子串递归调用,取满足条件的最长的子
LC3:找到最长不重复子串(滑动窗口思路) LC11:找到一组数a1,a2,a3,a4,a5的两个数,数字的值为墙的高度,使得与x轴构成的容器,盛水最多。 LC15:找到所有三元组,使得相加为0 LC16:三元组,使其和最接近target LC17:...