Editorial Issues - 567. Permutation in String

ejini6969 commented 1 month ago

LeetCode Username

https://leetcode.com/u/ejini6969/

Problem Number, Title, and Link

567. Permutation in String

Bug Category

Editorial

Bug Description

Approach 1 -> intro quote

Readers are still recommended to read it because it helps to understand the next following approaches.

should be

Readers are still recommended to read it because it helps to understand the following approaches.
Approach 1 -> Time complexity has no explanation, should be something equivalent like below:

Time Complexity: O(𝑁!) The permute method generates all possible permutations of the string s1. In a permutation problem, the number of ways to permute a string of length 𝑁 is 𝑁!. Each recursive call swaps characters at different positions to explore every possible permutation at each level of recursion. At the first level, there are 𝑁choices for which character to place in the first position. At the second level, there are 𝑁−1 choices for which character to place in the second position, and so on, leading to 𝑁! total recursive calls.
Approach 2 -> Algorithm
Approach 2 -> Time Complexity -> Lack of explanation and should only display the dominating term. Should be re-worded to something equivalent like below.

First, we sort s1 which takes O(l1 log(l1) ). Then, we iterate through a range of (l2 - l1 + 1) and within the loop, we sort a substring of length l1. This process takes O( (l2 - l1 + 1) * l1 log(l1) ) time. Overall, we combine both Time complexities -> O( (l2 - l1 + 1 + 1) * l1 log(l1) ) -> O( (l2 - l1) * l1 log(l1) )
Approach 2 -> Space complexity -> Lack of explicit mention of sorting in-place also requires additional space. Something equivalent like below should be incorporated with original explanation.

Some extra space is used when we sort an array of size N in place. The space complexity of the sorting algorithm depends on the programming language.

In Python, the sort method sorts a list using the Timsort algorithm which is a combination of Merge Sort and Insertion Sort and has a space complexity of O(N) In C++, the sort() function is implemented as a hybrid of Quick Sort, Heap Sort, and Insertion Sort, with a worst-case space complexity of O(logN) In Java, Arrays.sort() is implemented using a variant of the Quick Sort algorithm which has a space complexity of O(logN)
Approach 3 -> Wrong + Lack of Explanation for Time Complexity

should be O(l1 + (26 + l1) (l2 - l1)) since the process of storing the hashmap and looping of the inner-loop occurs at the same level, hence it should be addition instead of multiplication.

Also, Explanation on how to derive each individual's operations' complexity is required.
Approach 3 -> Wrong space complexity

The space complexity is not O(1) because it will change based on the input size given by l1 and l2. Within the inner-loop, we are doing O(26 * (l2 - l1)) in which the size of our space used to store each instance of hashmap is O(26) at worse, but we need to store l2 - l1 instances of hashmap at worse too.
Approach 4 -> Time Complexity -> Applies to the point same as approach 3
Approach 4 -> Space Complexity -> Applies to the point same as approach 3
Approach 5 -> Misleading term hashmap as the implementation uses a 26-length fixed-size array.
Approach 5 -> Lack of explanation on T.C and S.C
Approach 6 -> Missing explanations too
Approach 4 - 6 implementation should change variable name from s1map, s2map respectively to s1arr, s2arr since hashmap is not equivalent to a 26-length fixed-size array.

Language Used for Code

None

Code used for Submit/Run operation

No response

Expected behavior

Editorial should provide concise and latest info to user.

Screenshots

No response

Additional context

No response

exalate-issue-sync[bot] commented 1 month ago

LeetCode Support commented: Hello,

Your reported issue has been relayed to our team for thorough investigation. We appreciate your patience as we work to address and resolve this matter. We will reach out to you when we have updates regarding the issue.

If you have any further questions or concerns in the meantime, please feel free to let us know.

Best regards, LeetCode Support Team

exalate-issue-sync[bot] commented 1 month ago

Epiphania_Ekenimoh commented: Thank you for your time.

Your feedback has been used to enhance the problem. As a token of our appreciation, your LeetCode account has been credited with 100 LeetCoins.

If you have any more questions or additional feedback, please don't hesitate to let us know. Your continued support is invaluable to us!

Best regards, The LeetCode Team

ejini6969 commented 1 month ago

"* For approach 3, following should be updated too (add quotes around s1map and remove extra parenthesis)

Same applies to approach 4 below:
Approach 6 -> we do not check matches function within inner loop, so the extra 26 should be changed to 1 which is equivalent to O(l1 + (l2 - l1)).
Approach 6 -> algorithm explanation should be updated to s1arr and s2arr too.

exalate-issue-sync[bot] commented 1 month ago

Epiphania_Ekenimoh commented: Hello,

Your reported issue has been relayed to our team for thorough investigation. We appreciate your patience as we work to address and resolve this matter. We will reach out to you when we have updates regarding the issue.

If you have any further questions or concerns in the meantime, please feel free to let us know.

Best regards, LeetCode Support Team

algo74 commented 1 month ago

The time complexity for Approach 6 is not $O(l_1+26\times (l2 − l{1}))$ but $O(l_1 + l_2 + 26)$, although it simplifies to $O(l_2)$ anyway.

exalate-issue-sync[bot] commented 1 month ago

Epiphania_Ekenimoh commented: Hello there,

The issue you reported has been resolved. Please feel free to verify and retry.

We apologize for any inconvenience this may have caused and appreciate your patience while we worked to resolve the issue. If you have any further questions or concerns, please do not hesitate to contact us.

Thank you, LeetCode Support Team

ejini6969 commented 1 month ago

The last 2 suggestion for the latest post above are not implemented, please fix.

exalate-issue-sync[bot] commented 1 month ago

Epiphania_Ekenimoh commented: Hello,

Your reported issue has been relayed to our team for thorough investigation. We appreciate your patience as we work to address and resolve this matter. We will reach out to you when we have updates regarding the issue.

If you have any further questions or concerns in the meantime, please feel free to let us know.

Best regards, LeetCode Support Team

exalate-issue-sync[bot] commented 4 weeks ago

Epiphania_Ekenimoh commented: Hello there,

The issue you reported has been resolved. Please feel free to verify and retry.

We apologize for any inconvenience this may have caused and appreciate your patience while we worked to resolve the issue. If you have any further questions or concerns, please do not hesitate to contact us.

Best regards, LeetCode Support Team

LeetCode-Feedback / LeetCode-Feedback