2024 April 6 Problems
142 views
Skip to first unread message
daryl...@gmail.com
Apr 6, 2024, 12:34:44 PMApr 6
to leetcode-meetup
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.
Please post your solutions to this thread so others can use this as a reference.
2932Maximum Strong Pair XOR I75.6%Easy
2981Find Longest Special Substring That Occurs Thrice I41.9%Medium
2982Find Longest Special Substring That Occurs Thrice II33.0%Medium
Please download and import the following iCalendar (.ics) files to your calendar system.
Weekly: https://us04web.zoom.us/meeting/upIqc-6upj8sGt0O2fJXTw2gC4FxRMQ-iqAT/ics?icsToken=98tyKu6uqT8tHNyRthmOR7YAB4-gKO7xiCldjbcNs03jKRhndVHxFbZkKoBSIZXZJoin Zoom Meeting
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1
Meeting ID: 767 4768 4609
Passcode: 8wf3Qa
Reminder that we have the monthly meet up for coffee afterwards for anyone attending live.
Flocela Maldonado
Apr 6, 2024, 2:31:43 PMApr 6
to leetcode-meetup
2982Find Longest Special Substring That Occurs Thrice II33.0%Medium
class Solution {
public:
int maximumLength(string s) {
vector<unordered_map<int, int>> freqPerLengthPerChar(26, unordered_map<int, int>{});
int ltIdx = 0;
int rtIdx = 0;
while (ltIdx < s.size())
{
char ltChar = s[ltIdx];
char rtChar = s[rtIdx];
while (ltChar == rtChar)
{
++rtIdx;
if (rtIdx >= s.size())
{
break;
}
rtChar = s[rtIdx];
}
int length = rtIdx - ltIdx;
int charIdx = ltChar - 'a';
if (freqPerLengthPerChar[charIdx].find(length) == freqPerLengthPerChar[charIdx].end())
{
freqPerLengthPerChar[charIdx].insert({length,0});
}
++freqPerLengthPerChar[charIdx][length];
ltIdx += length;
}
int maxLength = -1;
int maxChar = -1;
for (int ii=0; ii<freqPerLengthPerChar.size(); ++ii)
{
if (freqPerLengthPerChar[ii].size() <= 0)
{
continue;
}
vector<int> lengths{};
for (auto p : freqPerLengthPerChar[ii])
{
lengths.push_back(p.first);
}
sort(lengths.begin(), lengths.end(),[](int a, int b){return a > b;});
int topLength = lengths[0];
int topLengthCount = freqPerLengthPerChar[ii][topLength];
if (topLengthCount >= 3)
{
if (topLength > maxLength)
{
maxLength = topLength;
}
}
else if (topLengthCount == 2)
{
int topLengthCountMinus1 = topLength - 1;
if (topLengthCountMinus1 > 0 && topLengthCountMinus1 > maxLength)
{
maxLength = topLengthCountMinus1;
}
}
else
{
int topLengthMinus2 = topLength - 2;
if (topLengthMinus2 > 0 && topLengthMinus2 > maxLength)
{
maxLength = topLengthMinus2;
}
}
if (lengths.size() >= 2)
{
int secondLength = lengths[1];
if (secondLength > maxLength)
{
maxLength = secondLength;
}
}
}
return maxLength;
}
};
Akash Agrawal
Apr 6, 2024, 2:36:03 PMApr 6
to leetcode-meetup
func maximumStrongPairXor(nums []int) int {
currentMaxXOR := 0
// sort the nums
sort.Slice(nums, func(i, j int) bool {return nums[i] < nums[j]})
// for a given number, the paired number lies between x/2 <= x <= 2*x
for idx, val := range nums {
// find left half using bs
leftIdx := bs(nums[:idx], (val+1)/2)
// find right half using bs
rightIdx := idx + bs(nums[idx+1:], val*2)
for idx := leftIdx; idx<= rightIdx; idx++ { //
if val^nums[idx] > currentMaxXOR {
currentMaxXOR = val^nums[idx]
}
}
}
return currentMaxXOR
}
func bs(data []int, x int) int {
return sort.Search(len(data), func(i int) bool { return data[i] >= x })
}
Flocela Maldonado
Apr 6, 2024, 9:04:45 PMApr 6
to leetcode-meetup
Time(O(n lg(n)). Memory(O(n)) Really could make time O(n) because there's no real reason to sort.
class Solution {
public:
// Each letter has a count (see counts vector inside maximumLength() function below).
// Each count keeps track of the longest string length for that letter. That longest string length is maxLength.
// Count also keeps track of how many times maxLength has been seen, that's the freqOfMaxLength.
// It also keeps track of how many times a string length of (maxLength - 1) has been seen. That is freqOfMinorLength.
struct Count
{
int maxLength = -1;
int freqOfMaxLength = 0;
int freqOfMinorLength = 0; // minor length is maxLength minus one.
void updateCount(int length)
{
if(length == maxLength)
{
// seeing this length again, so increase freqOfMaxLength.
++freqOfMaxLength;
}
else if(length == (maxLength-1))
{
// seeing this minor length again (maxLength -1), so increase freOfMinorLength.
++freqOfMinorLength;
}
else if (length > maxLength)
{
// length will become the new maxLength. If the old maxLength is one minus the length, then the old maxLength becomes
// the new minor length. So set the freqOfMinorLength to the current freqOfMaxLength.
// Update maxLength to length. And update freqOfMaxLength to one, it's the first time we see
// this length.
freqOfMinorLength = ((length - 1) == maxLength) ? freqOfMaxLength : 0;
maxLength = length;
freqOfMaxLength = 1;
}
}
};
int maximumLength(string s) {
// Every letter has a Count object.
vector<Count> counts(26, Count{});
int ltIdx = 0;
int rtIdx = 0;
// iterate across s. Count the length of each substring that has the same letter in it.
while (ltIdx < s.size())
{
// while the current letter on the right is equal to the ltChar, increase rtIdx.
char ltChar = s[ltIdx];
while (rtIdx < s.size() && s[rtIdx] == ltChar)
{
++rtIdx;
}
// the new length is rtIdx - ltIdx.
int length = rtIdx - ltIdx;
// update the Count at the letter corresponding to ltChar.
counts[ltChar - 'a'].updateCount(length);
ltIdx += length;
}
int finalAnswer = -1;
// Sort so that largest substring lengths are at the beginning of vector. That is sort so the largest count.maxLength is at the begininning of the vector.
sort(counts.begin(), counts.end(), [](const Count& a, const Count& b){return a.maxLength > b.maxLength;});
for(Count& count : counts)
{
// No need to continue if future Counts' maxLengths will be smaller than the current finalAnswer.
if(count.maxLength < finalAnswer)
{
break;
}
// The real frequency of the minor substring ( that is the substring with a length of maxLength-1) should be increased by the
// maxLength's frequency times 2. This is because inside the maxLength substring there are
// two substrings that have a length of maxLength-1.
count.freqOfMinorLength += (2 * count.freqOfMaxLength);
int curAns = -1;
if(count.freqOfMaxLength >= 3)
{
curAns = count.maxLength;
}
else if (count.freqOfMinorLength >= 3)
{
curAns = count.maxLength -1;
}
else
{
curAns = std::max(-1, count.maxLength - 2);
}
// maybe update finalAnswer with curAns
if(curAns > finalAnswer)
{
finalAnswer = curAns;
}
}
// returning zero isn't allowed.
return (finalAnswer == 0) ? -1 : finalAnswer;
}
};
Vivek H
Apr 6, 2024, 11:19:53 PMApr 6
to leetcod...@googlegroups.com
******************************************************************************************************
******************************************************************************************************
Time Complexity = O(n2)
class Solution {
public:
struct comp {
bool operator()(const pair<string, int>& p1, const pair<string, int>& p2)const {
if(p1.first.size() == p2.first.size())
return p1.second > p2.second;
return p1.first.size() > p2.first.size();
}
};
bool isSpecial(string s) {
int i=0; int j=s.length()-1;
while(i < j) {
if(s[i] != s[j])
return false;
i++;j--;
}
if(i==j && s[i] != s[0])
return false;
return true;
}
int maximumLength(string s) {
int len = s.length()/3 + 1;
set<pair<string, int>, comp> S;
map<string, int> M;
for(int i=0; i<s.length(); i++) {
for(int j=i; j<s.length(); j++) {
//cout << "i:" << i << " j:" << j << endl;
string str = s.substr(i, j-i+1);
//cout << "str:" << str << endl;
if(isSpecial(str)) {
M[str]++;
} else {
break;
}
}
}
for(auto &a : M) {
if(a.second >= 3) {
cout << a.first << " " << a.second << endl;
S.insert({a.first, a.second});
}
}
if(S.size() == 0)
return -1;
return S.begin()->first.size();
}
};
--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/1e89ee7c-75e6-4fa0-8fbb-7a2d84820f38n%40googlegroups.com.
vinay
Apr 7, 2024, 6:58:25 PMApr 7
to leetcod...@googlegroups.com
Used a Trie structure for this problem
The Trie should maintain the count of each special substring that appeared in the string
Each substring, if special (all chars remain same), is inserted in the Trie
During insertion, I'd get the count of that substring to get an idea of how many times it appeared in the string
If it appeared at least 3 times, I'd return the size of that substring.
class Solution {
public int maximumLength(String s) {
Trie root = new Trie('*');
int max = -1;
//Start with max possible substring and insert
//if count appears to be >= 3, you return the length of
//substring at the time
for(int i = s.length(); i >= 1; i--){
for(int j = 0; j <= s.length()-i; j++){
String subString = s.substring(j, j+i);
if(isSpecial(subString)){
int count = insert(root, subString);
if(count >= 3){
return subString.length();
}
}
}
}
return max;
}
//function to check if substring is special
public boolean isSpecial(String subString){
int[] hash = new int[26];
int count = 0;
for(char c : subString.toCharArray()){
hash[c-'a']++;
}
for(int num : hash){
if(num > 0){
count++;
}
}
return count == 1;
}
// function to insert a string into Trie
public int insert(Trie root, String s){
for(char c : s.toCharArray()){
if(root.children[c-'a'] == null){
root.children[c-'a'] = new Trie(c);
}
root = root.children[c-'a'];
}
root.count++;
return root.count;
}
//Trie class definition
public class Trie{
Trie[] children = null;
int count = 0;
char character;
public Trie(){}
public Trie(char c){
children = new Trie[26];
character = c;
}
}
}
--
Vivek H
Apr 7, 2024, 8:38:31 PMApr 7
to leetcod...@googlegroups.com
*************************************************************************************************
*************************************************************************************************
class Solution {
public:
int maximumLength(string s) {
map<string, int> special;
/* precompute all special strings */
int i = 0;
int j = 0;
while (i < s.length() && j < s.length()) {
if (s[i] == s[j]) {
j++;
} else {
// string str = s.substr(i, j - i);
string str = to_string(j - i) + s[i];
// cout << str << endl;
special[str]++;
i = j;
}
}
string str = to_string(j - i) + s[i];
// cout << "last:" << str << endl;
special[str]++;
map<string, int> M;
for (auto& a : special) {
//cout << a.first << " " << a.second << endl;
int num = stoi(a.first.substr(0, a.first.length() - 1));
char c = a.first[a.first.length() - 1];
int len = num;
M[a.first] = a.second;
for (int i = 1; i < num; i++) {
string str = to_string(i) + string(1, c);
//cout << "str:" << str << endl;
M[str] = M[str] + (a.second * len);
len--;
}
}
int maxLen = -1;
for (auto& a : M) {
//cout << a.first << " " << a.second << endl;
int num = stoi(a.first.substr(0, a.first.length() - 1));
//cout << "num:" << num << endl;
if (a.second >= 3) {
maxLen = max(maxLen, num);
} else {
if (num >= 3)
maxLen = max(maxLen, num - 2);
}
}
return maxLen;
}
};
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/CAMS9Bym_kYjTOKRwTFEZm77Z5d6AMtdoK2E%2BZUvuzYPMOEXvcg%40mail.gmail.com.
Reply all
Reply to author
Forward
0 new messages