# 159. (Locked)Longest Substring with At Most Two Distinct Characters

Difficulty: Hard

Frequency: N/A

Given a string S, find the length of the longest substring T that contains at most two distinct characters.

For example,
Given S = “eceba”,
T is “ece” which its length is 3.

Solution 1:
Data structure:
string, unordered_map
Steps:
1. Loop through the string using head and tail index to keep a sliding window.
2. For each char in the string
2.1 If it is not in the map, insert it, num_distinct++
2.2 map[s[tail]]++
2.3 while (num_distinct > 2) map[s[head]]–
2.3.1 If map[s[head]] == 0, num_distince–
2.4 max_length = max(tail – head + 1, max_length)
Complexity:
Runtime: O(n)
Space: O(n)
Test cases:
Corner cases:
Code:
```class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
int max_length = 0, head = 0, num_distinct = 0;
unordered_map&lt;char, int&gt; count_map;
for (int tail = 0; tail &lt; s.size(); tail++) {
if (!count_map.count(s[tail])) {
num_distinct++;
}
count_map[s[tail]]++;
while (distinct &gt; 2) {
num_distinct--;
i++;
}
max_length = max(max_length, tail - head + 1);
}
return max_length;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 013. Roman to Integer

Difficulty: Easy

Frequency: N/A

My solution:
Data structure:
unordered_map,string
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
Code:
```class Solution {
public:
int romanToInt(string s) {
unordered_map&lt;char, int&gt; roman_map = {{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000}};
int result = 0;
for (int i = 0; i &lt; s.size(); i++) {
if (i != s.size() &amp;&amp; roman_map[s[i]] &lt; roman_map[s[i + 1]]) {
result -= roman_map[s[i]];
} else {
result += roman_map[s[i]];
}
}
return result;
}
};
```
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

# 158. (Locked)Read N Characters Given Read4 II – Call multiple times

Difficulty: Hard

Frequency: N/A

Similar to Question [15. Read N Characters Given Read4], but the read function may be called multiple times.

My solution:
Data structure:
array
Steps:
1. Read from the internal buffer
2. Read from file
3. Push the superfluous to the internal buffer
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
Code:
```
class Solution {
private:
queue&lt;char&gt; leftover;

public:
int read(char *buf, int n) {
int read_sz = 0, actual_sz = 0;

// Read from the leftover
while (!leftover.empty()) {
if (actual_sz == n) return actual_sz;
buf[actual_sz++] = leftover.front();
leftover.pop();
}

// Read from the file
while (actual_sz &lt; n) {
if (read_sz &lt; 4) break;
}

// Push the leftover the queue
if (actual_sz &lt; n) {
for (int i = n; i &lt; actual_sz; i++) {
leftover.push(buf[i]);
}
}

int end = min(actual_sz, n);
buf[end] = '\0';
return end;
}
}

```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
code:

Things to learn:

# 157. (Locked)Read N Characters Given Read4

Difficulty: Easy

Frequency: N/A

The API: int read4(char *buf) reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there

is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note: The read function will only be called once for each test case.

My solution:
Data structure:
array
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
1. total length 102, try to read 103
2. total length 102, try to read 101
Code:
```
class Solution {
public:
int read(char *buf, int n) {
int total = 0;
bool eof = false;
while (!eof &amp;&amp; total &lt; n) {
if (return_sz &lt; 4) eof = true;
int need_size = min(read_sz, n - total);
total = total + need_size;
buf = buf + need_size;
}
}
}
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 151. Reverse Words in a String

Difficulty: Medium

Frequency: High

Given an input string, reverse the string word by word.

For example,
Given s = “`the sky is blue`“,
return “`blue is sky the`“.

Clarification:

• What constitutes a word?
A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

My solution:

data structure:

string

steps:

loop through the string in a reversed order.

1. append the word

2. append a space if there is a word followed

complexity:

Runtime: O(n)

Space: O(n)

Code:

```class Solution {
public:
void reverseWords(string &amp;s) {
int end = s.size();
string temp;
for (int i = end - 1; i &gt;= 0; i--) {
if (s[i] == ' ') {
end = i;
} else if (i == 0 || s[i - 1] == ' ') {
if (!temp.empty()) {
temp.append(1, ' ');
}
temp.append(s.substr(i, end - i));
}
}
s = temp;
}
};

```

Things to learn:

# 125. Valid Palindrome

Difficulty: Easy

Frequency: Medium

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
`"A man, a plan, a canal: Panama"` is a palindrome.
`"race a car"` is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

My solution:
data structure:
string
steps:
complexity:
Runtime: O(n)
Space: O(1)
Code:

```
class Solution {
public:
bool isPalindrome(string s) {
int i = 0, j = s.size() - 1;

while (i &lt; j) {
if (!isalnum(s[i])) {
i++;
continue;
}

if (!isalnum(s[j])) {
j--;
continue;
}

if (tolower(s[i]) == tolower(s[j])) {
i++;
j--;
} else {
return false;
}
}
return true;
}
};

```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
```
class Solution {
public:
bool isPalindrome(string s) {
for (int i = 0, j = s.size() - 1; i &lt; j; i++, j--) {
while (!isalnum(s[i]) &amp;&amp; i &lt; j) i++;
while (!isalnum(s[j]) &amp;&amp; i &lt; j) j--;
if (tolower(s[i]) != tolower(s[j])) return false;
}
return true;
}
};
```

Things to learn:

# 065. Valid Number

Difficulty: Easy

Frequency: Low

Validate if a given string is numeric.

Some examples:
`"0"` => `true`
`" 0.1 "` => `true`
`"abc"` => `false`
`"1 a"` => `false`
`"2e10"` => `true`

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Example Questions Candidate Might Ask:

Difficulty: Easy, Frequency: Low

Q: How to account for whitespaces in the string?
A: When deciding if a string is numeric, ignore both leading and trailing whitespaces.

Q: Should I ignore spaces in between numbers – such as “1 1”?
A: No, only ignore leading and trailing whitespaces. “1 1” is not numeric.

Q: If the string contains additional characters after a number, is it considered valid?

A: No. If the string contains any non-numeric characters (excluding whitespaces and decimal point), it is not numeric.

Q: Is it valid if a plus or minus sign appear before the number? A: Yes. “+1” and “-1” are both numeric.

Q: Should I consider only numbers in decimal? How about numbers in other bases such as hexadecimal (0xFF)?

A: Only consider decimal numbers. “0xFF” is not numeric.

Q: Should I consider exponent such as “1e10” as numeric?
A: No. But feel free to work on the challenge that takes exponent into consideration. (The Online Judge problem does take exponent into account.)

My solution:
Data structure:
string
Steps:
1. Ignore leading spaces
2. Handle the string before ‘e’
2.1 ‘+’ ‘-‘ is ok
2.2 Handle ‘.’
2.3 Handle digit
2.4 All the other characters are invalid
3. Handle the string after ‘e’
3.1 ‘+’ ‘-‘ is ok
3.2 Handle digit
3.3 All the other characters are invalid
4. Ignore the trailing spaces
Complexity:
Runtime: O(n)
Space: O(n)
Test cases:
“234”=> true
“-234” => true
`"0"` => `true`
`" 0.1 "` => `true`
`"abc"` => `false`
`"1 a"` => `false`
`"2e10"` => `true`
Corner cases:
. => false
e => false
+ => false
.5 => true
5. => true
e5 =>false
5e =>false
2.5.6 =>false
2ee6 =>false
2e-6 =>true
2E6 => false
2e.6 => false
2.e6 => true
Code:
```class Solution {
public:
bool isNumber(string s) {
bool ret = false;
// ignore the leading spaces
int i = s.find_first_not_of(' ');

// handle the string before 'e': '+' '-' at beginning is ok, '.' is ok.
if (i &lt; s.size() &amp;&amp; s[i] == '+' || s[i] == '-') {
i++;
}
while (i &lt; s.size() &amp;&amp; isdigit(s[i])) {
i++;
ret = true;
}

if (i &lt; s.size() &amp;&amp; s[i] == '.') {
i++;
while (i &lt; s.size() &amp;&amp; isdigit(s[i])) {
i++;
ret = true;
}
}
// handle 'e'
if (ret &amp;&amp; i &lt; s.size() &amp;&amp; s[i] == 'e') {
i++;
ret = false;
// handle the string after 'e': '+' '-' at beginning is ok
if (i &lt; s.size() &amp;&amp; s[i] == '+' || s[i] == '-') {
i++;
}
while (i &lt; s.size() &amp;&amp; isdigit(s[i])) {
i++;
ret = true;
}
}

// ignore the trailing spaces
while (i &lt; s.size() &amp;&amp; isspace(s[i])) {
i++;
}

return ret &amp;&amp; i == s.size();
}
};
```

Things to learn:
1. Implement after clarification.