2025 June 21 Problems

[daryl...@gmail.com]

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.

Hard problem has been rolled over for any one who wants to try the matrix multiplication approach.

3582. Generate Tag for Video Caption Easy 31.3%

3527. Find the Most Common Response Medium 74.8%

 3337. Total Characters in String After Transformations II Hard 58.3%

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-gKO7xiCldjbcNs03jKRhndVHxFbZkKoBSIZXZ

Join Zoom Meeting (Meeting starts at 11:30)
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1

Meeting ID: 767 4768 4609

[Anuj Patnaik]

class Solution:

def generateTag(self, caption: str) -> str:

words = caption.split()

if not words:

return "#"

final_str = ""

final_str += words[0].lower()

for i in range(1, len(words)):

final_str += words[i].capitalize()

cleaned_final_str = re.sub(r'[^a-zA-Z]', '', final_str)

cleaned_final_str = "#" + cleaned_final_str

return cleaned_final_str[0:100]

[Anuj Patnaik]

class Solution:

def matrix_multiplication(A, B):

row = len(A)

col = len(B[0])

inner = len(B)

mult_result = [[0] * col for _ in range(row)]

for i in range(row):

for j in range(col):

for k in range(inner):

mult_result[i][j] = (mult_result[i][j] + A[i][k] * B[k][j]) % (10 ** 9 + 7)

return mult_result

def matrix_exponential(A, t):

n = len(A)

exp = [[1 if i == j else 0 for j in range(n)] for i in range(n)]#Identity matrix

while t > 0:

if t % 2 == 1:#to take care of odd numbers

exp = Solution.matrix_multiplication(exp, A)

A = Solution.matrix_multiplication(A, A)

t = t//2

return exp

def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:

M = [[0] * 26 for _ in range(26)]#26 by 26 matrix

for i in range(26):

for j in range(nums[i]):

M[(i + j + 1) % 26][i] += 1#M[j][i] is num of times character i contributes to character j in one transformation

M_exp = Solution.matrix_exponential(M, t)

N = [[0] for _ in range(26)]

for ch in s:

N[ord(ch) - ord('a')][0] += 1#1 by 26 vector which is the frequency of each character in s

transformed = Solution.matrix_multiplication(M_exp, N)#frequency of each character

return sum(row[0] for row in transformed) % (10 ** 9 + 7)#sum up all the frequencies

[Anuj Patnaik]

class Solution:

def findCommonResponse(self, responses: List[List[str]]) -> str:

freq = defaultdict(int)

for i in responses:

unique = set()

for j in i:

if j not in unique:

unique.add(j)

freq[j] += 1

maxfreq = max(freq.values())

allkeys = freq.keys()

possible_candidates = []

for k in allkeys:

if freq[k] == maxfreq:

possible_candidates.append(k)

return min(possible_candidates)

[John Yang]

class Solution:

def generateTag(self, caption: str) -> str:

capitalizedList = map(lambda x: x.capitalize(), caption.split(" "))

res = "".join(capitalizedList)

return "#" + res[:1].lower() + res[1:99]

[Sourabh Majumdar]

Generate Tag for Video Caption:

class Solution {

public:

string generateTag(string caption) {

std::stringstream caption_stream(caption);

std::string token;

std::stringstream final_string_stream;

while(std::getline(caption_stream, token, ' ')) {

// convert a string into lower case.

std::transform(

token.begin(),

token.end(),

token.begin(),

[](unsigned char character) {

return std::tolower(character);

}

);

token[0] = std::toupper(token[0]);

final_string_stream << token;

}

// convert the final string

std::string final_string = final_string_stream.str();

final_string[0] = std::tolower(final_string[0]);

final_string = "#" + final_string;

return final_string.substr(0, 100);

}

};

[Samuel Yor]

Suspicious Content] Generate Tag for Video Caption:

class Solution: def generateTag(self, caption): import re # Step 1: Split into words words = caption.split() if not words: return "#" # Step 2: Convert to camelCase and prefix with # camel = words[0].lower() + ''.join(word.capitalize() for word in words[1:]) tag = '#' + camel # Step 3: Remove non-letters (except the first '#') cleaned = '#' + ''.join(ch for ch in tag[1:] if ch.isalpha()) # Step 4: Truncate to max 100 characters return cleaned[:100]

--
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 visit https://groups.google.com/d/msgid/leetcode-meetup/c20d725b-1f05-42e8-ba1b-c212e3256de3n%40googlegroups.com.

[John Yang]

class Solution:

def findCommonResponse(self, responses: List[List[str]]) -> str:

dedupSub = list(map(set, responses))

# print(list(dedupSub))

flat_list = [ele for sublist in dedupSub for ele in sublist]

# print(flat_list)

counts = collections.Counter(flat_list)

max_freq = max(counts.values())

candidates = [resp for resp, freq in counts.items() if freq == max_freq]

return min(candidates)

[Sourabh Majumdar]

Find Most common Response.

class Solution {

public:

struct Response{

std::string response;

int count;

};

struct ResponseComparator{

bool operator()(Response& response1, Response& response2) {

if (response1.count == response2.count) {

return response1.response > response2.response;

}

return response1.count < response2.count;

}

};

std::unordered_set<std::string> CollectAllUniqueResponses(

std::vector<std::string> responses_at_day

) {

std::unordered_set<std::string> unique_responses;

for(auto response : responses_at_day) {

unique_responses.insert(response);

}

return unique_responses;

}

string findCommonResponse(vector<vector<string>>& responses) {

std::unordered_map<std::string, int> response_count;

for(auto responses_at_day : responses) {

std::unordered_set<std::string> unique_responses = CollectAllUniqueResponses(responses_at_day);

for(auto unique_response : unique_responses) {

response_count[unique_response] +=1;

}

}

// Now I will use a priority queue.

std::priority_queue<Response, std::vector<Response>, ResponseComparator> response_priority_queue;

for(auto [response, count] : response_count) {

response_priority_queue.push(

Response{

.response = response,

.count = count

}

);

}

// now return the top

Response top_response = response_priority_queue.top();

return top_response.response;

}

};

[Samuel Yor]

#2 Finding the most common response


class Solution:
    def findCommonResponse(self, responses):
        freq = Counter()

        for daily in responses:
            unique = set(daily)  # remove duplicates within each day
            freq.update(unique)

        max_count = max(freq.values())
        candidates = [resp for resp, count in freq.items() if count == max_count]

        return min(candidates)  # lexicographically smallest

To view this discussion visit https://groups.google.com/d/msgid/leetcode-meetup/037b896e-5660-4e71-8ca9-325031ffda3cn%40googlegroups.com.

[Samuel Yor]

[Liam Kirsh]

#2 Find the Most Common Response - using Python's built in multi level sorting

from collections import defaultdict

class Solution:

def findCommonResponse(self, responses: List[List[str]]) -> str:

counter = defaultdict(int)

for day in range(len(responses)):

uniq = set(responses[day])

for response in uniq:

counter[response] += 1

# Now we want to sort the counts by primary key: count descending

# Secondary key: response ascending

items = counter.items() # returns a list of tuples (response, count)

# The Python sort function uses tuple indices in order as sort keys

# If we pass (count, response) we'll get increasing count, increasing response

# Let's pass negative count instead: then we'll get desc count, inc response

sorted_items = sorted([(-c, r) for (r, c) in items])

return sorted_items[0][1]

[daryl...@gmail.com]

3337. Total Characters in String After Transformations II Hard 58.3%

The hints for this problem suggest approaching it as a linear algebra problem. The idea is that we will have a vector representing the counts of each letter in s. When we do a transform, we want to find out what the counts will be in the new vector. We can represent by creating a matrix that represents the shift. Each row in the matrix will have a 1 for each letter added after the transfrom and 0 otherwise. Then when we multiply the vector against this matrix the product will have the counts of all the letters after a transform. We can repeat multiplying by the transform matrix every time we need to perform a transformation.

Since we multiplying the same matrix by itself over and over again, we can optimize this by doing repeated squaring. Instead of multiplying by X t times, we can instead do X*X to get X^2, then X^2 * X^2 to get X^4, then X^4 * X^4 to get get X^8. This way we're doubling the number of X's with each square. If it isn't an exact power of 2, then we can recursively do repeated squaring on the remaining multiplications. I've memorized the squares as we go to try to save some time on this recursion as well.

class Solution:

def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:

def matrixMultiply(a, b):

rows = len(a)

n = len(a[0])

cols = len(b[0])

result = [[0 for _ in range(cols)] for _ in range(rows)]

for m in range(rows):

for p in range(cols):

for ind in range(n):

result[m][p] += (a[m][ind] * b[ind][p]) % (10 ** 9 + 7)

return result

memoization = {}

def repeatedSquaring(a, x):

if x == 0:

# Identity matrix with 1 on the diagonal and 0 elsewhere. X * Identity = X for all X.

return [[1 if x == y else 0 for y in range(26)] for x in range(26)]

if x == 1:

return a

square = a

multiplications = 1

while 2 * multiplications <= x:

double = 2 * multiplications

if double in memoization:

square = memoization[double]

else:

square = matrixMultiply(square, square)

memoization[double] = square

multiplications = double

remainder = repeatedSquaring(a, x - multiplications)

product = matrixMultiply(square, remainder)

memoization[x] = product

return product

transformMatrix = [[0 for _ in range(26)] for _ in range(26)]

for ind in range(26):

for shift in range(nums[ind]):

transformMatrix[ind][(ind + shift + 1) % 26] += 1

result = [0] * 26

for letter in s:

result[ord(letter) - ord('a')] += 1

result = [result]

transforms = repeatedSquaring(transformMatrix, t)

result = matrixMultiply(result, transforms)

count = 0

for i in range(len(result)):

for j in range(len(result[i])):

count = (count + result[i][j]) % (10 ** 9 + 7)

return count

On Saturday, June 21, 2025 at 9:40:23 AM UTC-7 daryl...@gmail.com wrote:

[FloM]

3582. Generate Tag for Video Caption Easy 31.3%

Time: O(n) Mem: O(n)

class Solution {

public:

string generateTag(string caption) {

stringstream ss{};

ss << '#';

bool isStartOfWord = false;

int captionIdx = 0;

int tagIdx = 0;

while(tagIdx < 99 && captionIdx < caption.size())

{

char c = caption[captionIdx];

int cInt{c};

if ( ((cInt >= 65) && (cInt <= 90)) ||

((cInt >= 97) && (cInt <= 122))

)

{

if (tagIdx== 0)

{

ss << static_cast<char>(tolower(c));

}

else

{

if (isStartOfWord)

{

ss << static_cast<char>(toupper(c));

}

else

{

ss << static_cast<char>(tolower(c));

}

}

isStartOfWord = false;

++tagIdx;

}

else if (c == ' ')

{

isStartOfWord = true;

}

++captionIdx;

}

return ss.str();

}

};

[Roshan Sridhar]

1. class Solution:
2.     def generateTag(self, caption: str) -> str:

1.         words = caption.strip().split(" ")
2.         tag = []
3.         for i, word in enumerate(words):
4.             if not word:
5.                 continue
6.             if i == 0:
7.                 tag.append(word.lower())
8.             else:
9.                 tag.append(word.capitalize())
10.         return '#' + ''.join(tag)[:99]

[FloM]

3527. Find the Most Common Response Medium 74.8%

Time: O(log(n*m)) Mem: O(n*m) Where n*m is the number of surveys * num of responses in survey

class Solution {

public:

string findCommonResponse(vector<vector<string>>& responses) {

unordered_map<string, int> totalCountsPerString{};

for(int ii=0; ii<responses.size(); ++ii)

{

unordered_set<string> surveyResponses{};

for(int jj=0; jj<responses[ii].size(); ++jj)

{

surveyResponses.insert(responses[ii][jj]);

}

for(const string& response : surveyResponses)

{

++totalCountsPerString[response];

}

}

priority_queue<

pair<string, int>,

vector<pair<string, int>>,

decltype([]

(const pair<string, int>& a, const pair<string, int>& b)

{

if (a.second == b.second)

{

return a.first > b.first;

}

else

{

return a.second < b.second;

}

})

> pq{};

for(pair<string, int> strCount : totalCountsPerString)

{

pq.push(strCount);

}

return pq.top().first;

}

};