Skip to content

Commit 2f3a77d

Browse files
haoelhaoel
committed
New Problem Solution"Longest Substring with At Least K Repeating Characters"
1 parent cfe8809 commit 2f3a77d

3 files changed

Lines changed: 216 additions & 0 deletions

File tree

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,8 @@ LeetCode
88

99
| # | Title | Solution | Difficulty |
1010
|---| ----- | -------- | ---------- |
11+
|395|[Longest Substring with At Least K Repeating Characters](https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/) | [C++](./algorithms/cpp/longestSubstringWithAtLeastKRepeatingCharacters/LongestSubstringWithAtLeastKRepeatingCharacters.cpp)|Medium|
12+
|394|[Decode String](https://leetcode.com/problems/decode-string/) | [C++](./algorithms/cpp/decodeString/DecodeString.cpp)|Medium|
1113
|393|[UTF-8 Validation](https://leetcode.com/problems/utf-8-validation/) | [C++](./algorithms/cpp/UTF8Validation/UTF8Validation.cpp)|Medium|
1214
|392|[Is Subsequence](https://leetcode.com/problems/is-subsequence/) | [C++](./algorithms/cpp/isSubsequence/IsSubsequence.cpp)|Medium|
1315
|391|[Perfect Rectangle](https://leetcode.com/problems/perfect-rectangle/) | [C++](./algorithms/cpp/perfectRectangle/PerfectRectangle.cpp)|Hard|

‎algorithms/cpp/decodeString/DecodeString.cpp‎

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
// Source : https://leetcode.com/problems/decode-string/
2+
// Author : Hao Chen
3+
// Date : 2016-09-08
4+
5+
/***************************************************************************************
6+
*
7+
* Given an encoded string, return it's decoded string.
8+
*
9+
* The encoding rule is: k[encoded_string], where the encoded_string inside the square
10+
* brackets is being repeated exactly k times. Note that k is guaranteed to be a
11+
* positive integer.
12+
*
13+
* You may assume that the input string is always valid; No extra white spaces, square
14+
* brackets are well-formed, etc.
15+
*
16+
* Furthermore, you may assume that the original data does not contain any digits and
17+
* that digits are only for those repeat numbers, k. For example, there won't be input
18+
* like 3a or 2[4].
19+
*
20+
* Examples:
21+
*
22+
* s = "3[a]2[bc]", return "aaabcbc".
23+
* s = "3[a2[c]]", return "accaccacc".
24+
* s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
25+
***************************************************************************************/
26+
27+
class Solution {
28+
public:
29+
string decodeString(string s) {
30+
if (!isValid(s)) return "";
31+
32+
stack<string> _stack;
33+
stack<int> _nstack;
34+
35+
string result;
36+
string tmp;
37+
int n=0;
38+
for (int i=0; i<s.size(); i++) {
39+
40+
if ( isNum(s[i]) ) {
41+
n = 0;
42+
for(; isNum(s[i]); i++ ) {
43+
n = n*10 + s[i] - '0';
44+
}
45+
}
46+
47+
if (s[i] == '[') {
48+
tmp="";
49+
_stack.push(tmp);
50+
_nstack.push(n);
51+
} else if (s[i] == ']') {
52+
n = _nstack.top();
53+
tmp="";
54+
for (; n>0; n--) {
55+
tmp += _stack.top();
56+
}
57+
_stack.pop();
58+
_nstack.pop();
59+
if ( ! _stack.empty() ) {
60+
_stack.top() += tmp;
61+
}else {
62+
result += tmp;
63+
}
64+
} else {
65+
if ( ! _stack.empty() ) {
66+
_stack.top() += s[i];
67+
} else {
68+
result += s[i];
69+
}
70+
71+
}
72+
}
73+
74+
return result;
75+
}
76+
77+
private:
78+
79+
//only check the following rules:
80+
// 1) the number must be followed by '['
81+
// 2) the '[' and ']' must be matched.
82+
bool isValid(string& s) {
83+
stack<char> _stack;
84+
for (int i=0; i<s.size(); i++) {
85+
if ( isNum(s[i]) ) {
86+
for(; isNum(s[i]); i++);
87+
if (s[i] != '[') {
88+
return false;
89+
}
90+
_stack.push('[');
91+
continue;
92+
} else if (s[i] == ']' ) {
93+
if ( _stack.top() != '[' ) return false;
94+
_stack.pop();
95+
}
96+
}
97+
98+
return (_stack.size() == 0);
99+
}
100+
101+
bool isNum(char ch) {
102+
return (ch>='0' && ch<='9');
103+
}
104+
};
105+

‎algorithms/cpp/longestSubstringWithAtLeastKRepeatingCharacters/LongestSubstringWithAtLeastKRepeatingCharacters.cpp‎

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
// Source : https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
2+
// Author : Hao Chen
3+
// Date : 2016-09-08
4+
5+
/***************************************************************************************
6+
*
7+
* Find the length of the longest substring T of a given string (consists of lowercase
8+
* letters only) such that every character in T appears no less than k times.
9+
*
10+
* Example 1:
11+
*
12+
* Input:
13+
* s = "aaabb", k = 3
14+
*
15+
* Output:
16+
* 3
17+
*
18+
* The longest substring is "aaa", as 'a' is repeated 3 times.
19+
*
20+
* Example 2:
21+
*
22+
* Input:
23+
* s = "ababbc", k = 2
24+
*
25+
* Output:
26+
* 5
27+
*
28+
* The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3
29+
* times.
30+
***************************************************************************************/
31+
32+
const int NO_OF_CHARS = 256;
33+
34+
/* if every character appears at least k times, the whole string is ok.
35+
* Otherwise split by a least frequent character.
36+
*
37+
* Because it will always be too infrequent and thus can't be part of any ok substring
38+
* and make the most out of the splits.
39+
*/
40+
41+
42+
class Solution {
43+
public:
44+
int longestSubstring(string s, int k) {
45+
46+
//deal with edge cases
47+
if (s.size() == 0 || s.size() < k) return 0;
48+
if (k==1) return s.size();
49+
50+
//declare a map for every char's counter
51+
int count[NO_OF_CHARS];
52+
memset(count , 0, sizeof(count));
53+
54+
//counting every char
55+
for (char ch : s) {
56+
count[ch]++;
57+
}
58+
59+
int i=0;
60+
for ( i=0; i<NO_OF_CHARS; i++) {
61+
if (count[i] !=0 && count[i] < k) break;
62+
}
63+
//all of the chars meet the requirement
64+
if ( i >= NO_OF_CHARS ) return s.size();
65+
66+
// find the most infrequent char
67+
char least = 0;
68+
for (int c = 0; c < NO_OF_CHARS; c++) {
69+
if (count[c] == 0) continue;
70+
if (least == 0) {
71+
least = c;
72+
} else if ( count[c] < count[least]) {
73+
least = c;
74+
}
75+
}
76+
77+
//split the string and run them recursively
78+
vector<string> subs;
79+
split(s, least, subs);
80+
81+
int res = 0;
82+
for (string str: subs) {
83+
res = max(res, longestSubstring(str, k));
84+
}
85+
return res;
86+
return 0;
87+
}
88+
89+
private:
90+
91+
inline int max(int x, int y) { return x>y? x:y; }
92+
93+
inline void split(const string &s, char delim, vector<string> &elems) {
94+
stringstream ss;
95+
ss.str(s);
96+
string item;
97+
while (getline(ss, item, delim)) {
98+
cout << item << endl;
99+
elems.push_back(item);
100+
}
101+
}
102+
103+
104+
inline vector<string> split(const string &s, char delim) {
105+
vector<string> elems;
106+
split(s, delim, elems);
107+
return elems;
108+
}
109+
};

0 commit comments

Comments
 (0)