Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC"
.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string ""
.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
两个指针,start,end。end往后面搜。存在满足要求的后,尽量压缩start。
class Solution { public: string minWindow(string S, string T) { int c[256] = {0}; bool cb[256] = {0}; int cnt = T.size(); for (char i: T) c[(int)i]++, cb[(int)i] = true; int start = 0, end = 0; int ls = S.size(); int minlen = 10000; string minstr = ""; while (end < ls && start < ls) { if (cb[S[end]]) { c[S[end]]--; if (c[S[end]] >= 0) cnt--; while (cnt == 0) { if (cb[S[start]] == false) start++; else if (c[S[start]] < 0) { c[S[start]]++; start++; } else { break; } } if (cnt == 0) { if (end - start + 1 < minlen) { minlen = end - start + 1; minstr = S.substr(start, minlen); } c[S[start]]++; start++; cnt++; } } end++; } return minstr; } };
相关推荐
leetcode76 LeetCode76_MinimumWindowSubstring
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...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
leetcode 分类 Leetcode Introduction 本文旨在将leetcode的题型分类 Pattern: Sliding window 滑动窗口类型的题目经常是用来执行数组或是链表上某个区间(窗口)上的操作。比如找最长的全为1的子数组长度。滑动窗口...
java lru leetcode Fighting for a job! 记录找工作期间搬运的题,全部使用Java实现,本人C++鶸 1 ...LeetCode ...Substring Without Repeating Characters LeetCode 13 Roman to Integer LeetCode 6 Zi
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
411 | [Minimum Unique Word Abbreviation](https://leetcode.com/problems/minimum-unique-word-abbreviation/) | [C++](./C++/minimum-unique-word-abbreviation.cpp) [Python](./Python/minimum-unique-word-...
Minimum Window Substring 两个指针遍历 map Maximal Rectangle 栈 局部递增 或者 动态规划 Binary Tree Inorder Traversal 栈 递归 Single Number 异或 Copy List with Random Pointer 单链表 map Max Points on a ...
leetcode中文版
vs code LeetCode 插件
答案LeetCode-Longest_Substring_Without_Repeating_Characters 这是LeetCode上“最长子串无重复字符”问题的解决方案。 问题描述:给定一个字符串,求没有重复字符的最长子串的长度。 示例 1:输入:“abcabcbb” ...
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
leetcode添加元素使和等于 经验教训 一定要吧功能尽量细化为函数,这样一者做题思路比较清晰,二者可以在某些情况下直接return值。 如果输入的形式是一个序列,则可以想想:分治、动规、贪婪,一般不建议搜索,因为...
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...