给定一个字符串 s ,找出其中不含有重复字符的最长子串的长度代码c语言
时间: 2024-10-20 11:10:16 浏览: 19
leetcode #3 无重复字符的最长子串(C)
在C语言中,可以使用滑动窗口(Sliding Window)算法来解决这个问题。滑动窗口是一种常见的动态规划思想,通过维护一个字符集窗口,每次检查新字符是否已经在集合中,如果不在则加入窗口并更新最大长度,如果在则移除窗口左侧的第一个已重复字符。
下面是一个简单的C语言函数实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_CHAR 128
int lengthOfLongestSubstring(char* s) {
int n = strlen(s);
bool char_set[MAX_CHAR] = {false}; // 用于记录字符是否出现过
int left = 0, right = 0;
int maxLength = 0;
while (right < n) {
if (!char_set[s[right]]) {
// 如果字符未出现,则添加到窗口
char_set[s[right]] = true;
maxLength = max(maxLength, right - left + 1); // 更新最大长度
right++;
} else {
// 如果字符已经出现,移除左侧的重复字符
char_set[s[left]] = false; // 将左边界字符设回未出现
left++; // 移动左边界
}
}
return maxLength;
}
// 辅助函数,返回两个数的最大值
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
char str[] = "abcabcbb";
printf("Length of the longest substring without repeating characters: %d\n", lengthOfLongestSubstring(str));
return 0;
}
```
在这个代码中,`lengthOfLongestSubstring` 函数接收一个字符串指针,通过双指针 `left` 和 `right` 的移动,不断更新不含重复字符的子串的左右边界,并计算其长度。
阅读全文