Link here I'm currently learning c++ coming from a python background, so I'll include a solution in python and in c++ for the following problem statement and based on very helpful answers obtained on my previous question I made some improvements in the c++ implementation:
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb" Output: 3
Example 2:
Input: s = "bbbbb" Output: 1
I would like to improve speed for both python and c++ implementations, and I need to improve memory consumption in the c++ implementation since I got a very high figure (600+ MB) as well as the reasons for this high consumption (if the figure is accurate), and I would like general suggestions too.
longest_substring.py
def get_longest(s: str):
possibilities = (s[i:] for i in range(len(s)))
maximum = 0
for possibility in possibilities:
end_idx = maximum
while end_idx <= len(possibility):
current_chunk = possibility[0:end_idx]
end_idx += 1
if not (current_size := len(current_chunk)) == len(set(current_chunk)):
break
maximum = max(current_size, maximum)
return maximum
if __name__ == '__main__':
print(f'Longest substring:\n{get_longest("abcabcbb")}')
Leetcode stats:
Runtime: 260 ms, faster than 19.36% of Python3 online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 14.4 MB, less than 100.00% of Python3 online submissions for Longest Substring Without Repeating Characters.
longest_substring.h
#ifndef LEETCODE_LONGEST_SUBSTRING_H
#define LEETCODE_LONGEST_SUBSTRING_H
#include <string>
int longest_sub(const std::string &s);
bool check_unique(const std::string &s);
#endif //LEETCODE_LONGEST_SUBSTRING_H
longest_substring.cpp
#include "longest_substring.h"
#include <iostream>
using std::endl;
using std::cout;
using std::string;
bool check_unique(const string &s) {
for (size_t i = 0; i < s.size() - 1; ++i) {
for (size_t j = i + 1; j < s.size(); ++j) {
if (s[i] == s[j])
return false;
}
}
return true;
}
int longest_sub(const string &s) {
int maximum = 0;
for (size_t i = 0; i < s.size(); ++i) {
const string possibility = s.substr(i);
auto end_idx = maximum;
while (end_idx < possibility.size()) {
const string current_chunk = possibility.substr(0, ++end_idx);
if (!check_unique(current_chunk))
break;
auto current_size = current_chunk.size();
if (current_size > maximum)
maximum = current_size;
}
}
return maximum;
}
int main() {
cout << "Longest substring: " << endl;
cout << longest_sub("abcabcbb");
}
Leetcode stats:
Runtime: 100 ms, faster than 14.88% of C++ online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 604.2 MB, less than 5.02% of C++ online submissions for Longest Substring Without Repeating Characters.