2024 May 25 Problems
65 views
Skip to first unread message
daryl...@gmail.com
May 25, 2024, 12:52:42 PMMay 25
to leetcode-meetup
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.
3042Count Prefix and Suffix Pairs I64.4%Easy
3084Count Substrings Starting and Ending with Given Character48.8%Medium
Join Zoom Meeting (Meeting starts at 11:30)
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.
3042Count Prefix and Suffix Pairs I64.4%Easy
3084Count Substrings Starting and Ending with Given Character48.8%Medium
3045Count Prefix and Suffix Pairs II23.6%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 (Meeting starts at 11:30)
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1
Meeting ID: 767 4768 4609
Passcode: 8wf3Qa
Flocela Maldonado
May 25, 2024, 12:58:29 PMMay 25
to leetcode-meetup
June 4th - First Saturday of the Month - Meet at MeetFresh after the Leetcode discussion.
Vivek H
May 25, 2024, 1:21:26 PMMay 25
to leetcod...@googlegroups.com
**************************************************************************************************
****************************************************************************************************
Used simple maths to solve it. we just have to find the number of pairs of indices of c in a string
for eg if s =zzz , c = z
possible pairs of indices are = (0,0)(0,1), (0,2), (1,1),(1,2),(2,2) = 6
so mathematically if n is no of indices of c in s. then total substring will be:
n + n-1 + n-2 ....+ 1
= n(n+1) / 2
class Solution {
public:
long long countSubstrings(string s, char c) {
map<char, vector<int>> M;
for (int i = 0; i < s.length(); i++) {
if (s[i] == c)
M[c].push_back(i);
}
long long n = M[c].size();
if (n == 0)
return 0;
else if (n < 2)
return 1;
return (n * (n+1))/2;
}
};
--
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/30869825-dfc6-4f0c-8cda-2539cfb2a791n%40googlegroups.com.
Vivek H
May 25, 2024, 1:43:41 PMMay 25
to leetcod...@googlegroups.com
*************************************************************************************************************
*************************************************************************************************************
class Solution {
public:
bool isPrefix(string& s, string& target) {
if(s.length() > target.length())
return false;
int i = 0;
int j = 0;
while (i < s.length()) {
if (s[i] != target[j])
return false;
i++; j++;
}
return true;
}
bool isSuffix(string& s, string& target) {
if(s.length() > target.length())
return false;
int i = s.length() - 1;
int j = target.length()-1;
while (i >= 0) {
if (s[i] != target[j])
return false;
i--; j--;
}
return true;
}
bool comp(string& s1, string& s2) { return s1.length() < s2.length(); }
int countPrefixSuffixPairs(vector<string>& words) {
//sort(words.begin(), words.end());
int count = 0;
for(int i=0; i<words.size()-1; i++) {
for(int j=i+1; j<words.size(); j++) {
if(isPrefix(words[i], words[j]) && isSuffix(words[i], words[j])) {
count++;
}
}
}
return count;
}
};
Allen S.
May 25, 2024, 2:02:32 PMMay 25
to leetcode-meetup
EASY LEVEL:
func countPrefixSuffixPairs(words []string) int {
// O(n*n) solution
count := 0
for i := range words {
for j := i + 1; j < len(words); j++ {
if isPrefixAndSuffix(words[i], words[j]) {
count++
}
}
}
return count
}
func isPrefixAndSuffix(str1, str2 string) bool {
if len(str1) <= len(str2) &&
str1 == str2[:len(str1)] &&
str1 == str2[len(str2)-len(str1):] {
return true
}
return false
}
Allen S.
May 25, 2024, 2:02:57 PMMay 25
to leetcode-meetup
MEDIUM LEVEL
func countSubstrings(s string, c byte) int64 {
var countChar int64 = 0
for i := range s {
if s[i] == c {
countChar++
}
}
var countSubstr int64 = 0
for i := range countChar { // from 0 to countChar - 1
countSubstr = countSubstr + 1 + i
}
return countSubstr
// return countChar*(countChar+1)/2;
}
// a - 0 + 1 + 0 = 1
// aa - 1 + 1 + 1 = 3
// aaa - 3 + 1 + 2 = 6
// aaaa - 6 + 1 + 3 = 11
// a a a a
// a a a a
// a a a a
// a a a a
Gowrima Jayaramu
May 25, 2024, 2:04:32 PMMay 25
to leetcode-meetup
def countPrefixSuffixPairs(self, words: List[str]) -> int:
i, j = 0, 0
count = 0
while i<len(words):
j = i+1
str1 = words[i]
while j<len(words):
str2 = words[j]
#check if str1 is prefix and suffix of str2
if str2.startswith(str1) and str2.endswith(str1):
count += 1
j += 1
i += 1
return count
Space: O(1)
Thank you,
gowrima
vinay
May 25, 2024, 2:19:13 PMMay 25
to leetcod...@googlegroups.com
Tracking the indexes and adding the size of indexes every time we see the substring ended with char c
Input: s = "abada", c = "a"
abada -> list size = 1, count = 1
abada ->list size = 2 , count = 3 etc
time o(n), space o(n)
class Solution {
public long countSubstrings(String s, char c) {
List<Integer> indexes = new ArrayList<>();
int index = 0;
long count = 0;
for( char sc : s.toCharArray()){
if(sc == c){
indexes.add(index);
count += indexes.size();
}
index++;
}
return count;
}
}
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/6e03737a-7e93-4e45-993d-e18574216d11n%40googlegroups.com.
Yogesh Mundada
May 25, 2024, 3:12:59 PMMay 25
to leetcode-meetup
Isn't this n^3?
On Saturday, May 25, 2024 at 10:43:41 AM UTC-7 V H wrote:
Message has been deleted
Priyank Gupta
May 25, 2024, 3:43:10 PMMay 25
to leetcode-meetup
'''
Time : O(n**2 + K) => O(n**2)
Space: O(K)
n => no of elements in words
k => len of longest string in words
'''
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
res = 0
for i in range(len(words)):
for j in range(i+1, len(words)):
if self.isValid(words[i], words[j]):
res += 1
return res
def isValid(self, str1, str2):
if len(str1) > len(str2):
return False
if len(str1) == len(str2):
if str1 == str2:
return True
return False
prefix = str2[:len(str1)]
suffix = str2[len(str2)-len(str1):]
if prefix == str1 and suffix == str1:
return True
return False
'''
Time : O(n)
space: O(1)
'''
class Solution:
def countSubstrings(self, s: str, c: str) -> int:
match = 0
for i in range(len(s)):
if s[i] == c:
match += 1
res = 0
for i in range(len(s)):
if s[i] == c:
res += match
match -= 1
return res
vinay
May 26, 2024, 12:48:35 AMMay 26
to leetcod...@googlegroups.com
time complexity: o(n^2 *m) m is the longest string's length
space: o(1)
class Solution {
public int countPrefixSuffixPairs(String[] words) {
int count = 0;
for(int i = 0; i < words.length; i++){
for(int j = i+1; j < words.length; j++){
if(isPrefixAndSuffix(words[i], words[j])){
count++;
}
}
}
return count;
}
public boolean isPrefixAndSuffix(String s1, String s2){
if(s1.length() > s2.length()){
return false;
}else{
int s2len = s2.length();
for(int i = 0; i < s1.length(); i++){
if(s1.charAt(i) != s2.charAt(i)){
return false;
}
if(s1.charAt(i) != s2.charAt(s2len-s1.length()+i)){
return false;
}
}
}
return true;
}
}
Reply all
Reply to author
Forward
0 new messages