“This is the 13th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 73rd day 🎈!
🚀 Algorithm 🚀

🌲 The longest palindrome string

Given a string containing both uppercase and lowercase letters, find the longest palindrome string constructed from these letters.

Pay attention to case sensitivity during construction. For example, “Aa” cannot be treated as a palindrome string.

Note: The string is assumed to be no longer than 1010.

Example 1:

Input:"abccccdd"Output:7Explanation: The longest palindrome string we can construct is"dccaccd"And its length is 17.Copy the code

🌻C# method: sort traversal

  • When you see a problem, you can sort it first and compare it with traversal
  • This value is the result of different returns.

Code:

public class Solution {
    public int LongestPalindrome(string s) {
        int len = 0;
        HashSet<char> charSet = new HashSet<char> ();for (int i = 0; i < s.Length; ++i) {
            char c = s[i];
            if (charSet.Contains(c)) {
                len += 2;
                charSet.Remove(c);
            } else{ charSet.Add(c); }}if (charSet.Count > 0) {
            ++len;
        }
        returnlen; }}Copy the code

The execution result

By execution time:68Ms, in all C# beat 64.50% of users in submissionMemory consumption:34.9MB, in all CBeat 15.50% of users in submission
Copy the code

🌻Java Method 1: Count

Code:

class Solution {
    public int longestPalindrome(String s) {
        int[] count = new int[128];
        int length = s.length();
        for (int i = 0; i < length; ++i) {
            char c = s.charAt(i);
            count[c]++;
        }

        int ans = 0;
        for (int v: count) {
            ans += v / 2 * 2;
            if (v % 2= =1 && ans % 2= =0) { ans++; }}returnans; }}Copy the code

The execution result

By execution time:2Ms, beat out all Java commits71.26% user memory consumption:36.5MB, beat out all Java commits80.05% of the userCopy the code

Complexity analysis

Time complexity: O(N) Space complexity: O(S)Copy the code

💬 summary

  • Today is the seventy-third day of buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!