2024 March 23 Problems
78 views
Skip to first unread message
daryl...@gmail.com
Mar 23, 2024, 12:52:03 PMMar 23
to leetcode-meetup
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.
Join Zoom Meeting
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1
Meeting ID: 767 4768 4609
Passcode: 8wf3Qa
Please post your solutions to this thread so others can use this as a reference.
Hard problem has been rolled over from last week.
2697Lexicographically Smallest Palindrome81.1%Easy
2375Construct Smallest Number From DI String75.5%Medium
2790Maximum Number of Groups With Increasing Length19.4%Hard
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
Andriy T
Mar 23, 2024, 1:42:46 PMMar 23
to leetcode-meetup
Time O(n) Space O(n)
class Solution {
public String makeSmallestPalindrome(String s) {
int p1 = 0, p2 = s.length() - 1;
StringBuilder sb = new StringBuilder(s);
while (p1 < p2) {
char lc = s.charAt(p1);
char rc = s.charAt(p2);
if (lc != rc) {
if (rc <= lc) {
sb.setCharAt(p1, rc);
}
else {
sb.setCharAt(p2, lc);
}
}
p1++;
p2--;
}
return sb.toString();
}
}
Andriy T
Mar 23, 2024, 2:23:10 PMMar 23
to leetcode-meetup
2375Construct Smallest Number From DI String75.5%Medium
Time O(n^2) beats 74% in java, Space O(n)
class Solution {
public String smallestNumber(String pattern) {
int n = pattern.length();
int[] nums = new int[n + 1];
for (int i = 0; i<=n;i++) {
nums[i] = i + 1;
}
boolean swapping = true;
while (swapping) {
swapping = false;
for (int i = 0;i<n;i++) {
char ch = pattern.charAt(i);
int num1 = nums[i];
int num2 = nums[i+1];
if (ch == 'I' & num1 > num2) {
nums[i] = num2;
nums[i+1] = num1;
swapping = true;
}
else if (ch == 'D' & num2 > num1) {
nums[i+1] = num1;
nums[i] = num2;
swapping = true;
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i<n+1;i++){
sb.append(nums[i]);
}
return sb.toString();
}
}
Flocela Maldonado
Mar 23, 2024, 2:23:34 PMMar 23
to leetcode-meetup
Time O(n), Memory O(n), Have to create a string to return
class Solution {
public:
string smallestNumber(string pattern) {
string str = "";
int usedHigher = 0;
for(int ii=0; ii<pattern.size(); ++ii)
{
if(pattern[ii] == 'I')
{
str.append(to_string(usedHigher + 1));
++usedHigher;
}
else
{
int DCount = 0;
int jj = ii;
while (jj < pattern.size())
{
if(pattern[jj] == 'D')
{
++DCount;
}
else
{
break;
}
++jj;
}
int appendNum = usedHigher + DCount + 1;
str.append(to_string(appendNum));
usedHigher = appendNum;
--appendNum;
for(int kk=0; kk<DCount; ++kk)
{
str.append(to_string(appendNum));
--appendNum;
++ii;
}
}
}
if (pattern[pattern.size()-1] == 'I')
{
str.append(to_string(usedHigher + 1));
}
return str;
}
};
Gayathri Ravichandran
Mar 23, 2024, 3:15:11 PMMar 23
to leetcode-meetup
2375
Priyank Gupta
Mar 23, 2024, 3:21:33 PMMar 23
to leetcode-meetup
# Time : O(n)
# Space: O(n)
class Solution:
def makeSmallestPalindrome(self, s: str) -> str:
start = 0
end = len(s)-1
res = 0
s = list(s)
while(start < end):
if s[start] != s[end]:
if s[start] < s[end]:
s[end] = s[start]
else:
s[start] = s[end]
start += 1
end -= 1
return "".join(s)
daryl...@gmail.com
Mar 23, 2024, 3:21:51 PMMar 23
to leetcode-meetup
Following the meeting discussion, people are interested in the hard problem, so I will be rolling it over again to next week.
On Saturday, March 23, 2024 at 9:52:03 AM UTC-7 daryl...@gmail.com wrote:
Flocela Maldonado
Mar 23, 2024, 3:23:32 PMMar 23
to leetcode-meetup
Solution for the Hard Problem: Look for this title with xmmm0 as the author.
🔥 Detailed and Easy Explanation of Greedy Method || Python3
xmmm0
This post might give some insight too:
-Flo
On Saturday, March 23, 2024 at 12:15:11 PM UTC-7 Gayathri Ravichandran wrote:
Vivek H
Apr 5, 2024, 5:06:42 PMApr 5
to leetcod...@googlegroups.com
I attempted a greedy solution, basically using a heap sorted by the usageLimit and forming the groups by taking out one number at a time, but the last 10 test cases are TLE. Need to think harder to have those cases pass.
class Solution {
public:
struct comp {
bool operator()(const pair<int, int>& p1,
const pair<int, int>& p2) const {
if (p1.second == p2.second) {
return p1.first < p2.first;
} else {
return p1.second > p2.second;
}
}
};
int maxIncreasingGroups(vector<int>& usageLimits) {
set<pair<int, int>, comp> S;
for (int i = 0; i < usageLimits.size(); i++) {
S.insert({i, usageLimits[i]});
}
int groupSize = 1;
int maxGroups = 0;
while (1) {
if (groupSize > S.size())
break;
vector<int> V;
vector<pair<int, int>> P;
for (int i = 0; i < groupSize; i++) {
auto it = S.begin();
int num = it->first;
int limit = it->second;
limit--;
S.erase(it);
if (limit > 0)
P.push_back({num, limit});
}
maxGroups++;
// put the pairs back in S;
for (auto& a : P) {
S.insert({a.first, a.second});
}
// increase the groupSize
groupSize++;
}
return maxGroups;
}
};
--
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/83704083-36a1-4186-a143-c1308b2250dfn%40googlegroups.com.
Reply all
Reply to author
Forward
0 new messages