Find the Longest Common Prefix in C#

In this article, we will see the longest common prefix in C#

Problem Description

Write a function to find the longest common prefix string amongst all the arrays of strings in C#.

If there is no any common prefix then return an empty string "".

The solution to finding the Longest Common Prefix

Input Example

Example 1

Let the set of strings be { "flower", "flight", "fly", "flow" };

The longest common prefix here is "fl"

Example 2

Let the set of strings be {"dot", "dog", "donkey", "door", "cat" } there is no common prefix here so the longest common prefix is "", which means, an empty string.

Since there is no common prefix at all. 

To find the longest common prefix of a given set of strings in C#, you can use the following algorithm:

1. Initialize a variable prefix to an empty string.
2. If the input array is empty, return the empty string.
3. Sort the input array in lexicographic order.
4. Iterate over the characters in the first string in the sorted array.
5. For each character, compare it to the corresponding character in the other strings in the array. If any of the characters don't match, return the current prefix.
6. If all the characters match, append the current character to the prefix.
7. Return the prefix.

Here is the C# code that implements this algorithm:

public class LongestCommonPrefix {
    public static string LongestCommonPrefixFun(string[] input) {
        if (input.Length == 0) {
            return "";
        }
        Array.Sort(input);
        string prefix = "";
        for (int i = 0; i < input[0].Length; i++) {
            char c = input[0][i];
            for (int j = 1; j < input.Length; j++) {
                if (i >= input[j].Length || input[j][i] != c) {
                    return prefix;
                }
            }
            prefix += c;
        }
        return prefix;
    }
}

C#

You can call this method with an array of strings as an argument, like this:

string[] input = { "flower", "flight", "fly", "flow" };
string result = LongestCommonPrefix.LongestCommonPrefixFun(input);
Console.WriteLine("Longest Common Prefix is- " + result); // Output: "fl"

C#

This code will output "fl", which is the longest common prefix of the input strings "flower", "flight", "flow", and "flight".

Output

-----------------------------------------------------

Job Sequencing Problem in C#

  In this article we will discuss the Job sequencing problem in C#, we will achieve it using a greedy approach algorithm.

Problem statement

The job sequencing problem is a common problem that contains assigning a set of jobs to a set of machines, where each job has a deadline and a profit, and we have to get the maximum profit before the job deadline.

Given an array of jobs where each job has its deadline and profit. And Profit can get only if the job is finished before the job deadline also every job takes a single unit of time, so the minimum possible deadline for any job is 1 so we have to get the maximum profit before the job deadline.

For example,

JobID	Deadline	Profit
1	3	90
2	1	20
3	2	30
4	1	25
5	2	15

Output

JobID:-> 4,3,1

C# code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace JobsSequencingProblemInCSharp {
    public class Jobs {
        public int JobsID {
            get;
            set;
        }
        public int Deadline {
            get;
            set;
        }
        public int Profit {
            get;
            set;
        }
    }
    public class JobsSequencingProblem {
        public static void JobsSequencing() {
            List < Jobs > Jobs = new List < Jobs > () {
                new Jobs {
                    JobsID = 1, Deadline = 3, Profit = 90
                },
                new Jobs {
                    JobsID = 2, Deadline = 1, Profit = 20
                },
                new Jobs {
                    JobsID = 3, Deadline = 2, Profit = 30
                },
                new Jobs {
                    JobsID = 4, Deadline = 1, Profit = 25
                },
                new Jobs {
                    JobsID = 5, Deadline = 2, Profit = 15
                }
            };
            // Sort Jobs in the decreasing order of profit
            Jobs = Jobs.OrderByDescending(j => j.Profit).ToList();
            // Determine the maximum deadline of job
            int maxDeadline = Jobs.Max(j => j.Deadline);
            // Initialize the slots array
            int[] slots = new int[maxDeadline];
            foreach(Jobs Job in Jobs) {
                int slot = -1;
                for (int i = Job.Deadline - 1; i >= 0; i--) {
                    if (slots[i] == 0) {
                        slot = i;
                        break;
                    }
                }
                // If the slot is available, assign the Jobs to that slot
                if (slot != -1) {
                    slots[slot] = Job.JobsID;
                }
            }
            Console.WriteLine("Selected Jobs:");
            for (int i = 0; i < maxDeadline; i++) {
                if (slots[i] != 0) {
                    Console.WriteLine("Jobs " + slots[i]);
                }
            }
        }
    }
}
Public static void Main(string[] args) {
    JobsSequencingProblem.JobsSequencing();
    Console.ReadLine();
}

C#

Problem Explanation

This implementation is done by the greedy approach; we start by sorting the jobs in the decreasing order of the profit and then we determine the maximum deadline of the job then we initialize an array of slots with a length equal to the maximum deadline.

And then we iterate through each job and find the latest available slot for that job by starting from its deadline and going backward until we find an empty slot. If we find an available slot, we assign the job to that slot. If we don't find an available slot, we skip the job.

Finally, we print the selected jobs by iterating through the slots array and printing the job ID for each non-zero slot.

 

------------------------------------------

Rod Cutting Problem in C#

 The rod-cutting problem is the classic dynamic programming problem. In this problem, we cut a rod of a given length into smaller pieces with certain prices for each piece.

As per this problem, we need to determine the maximum revenue profit that can be get by cutting up the rod and selling the pieces of rod.

Problem statement

Given a rod of length n and we need to cut the rod in such a way that we need to sell it for the maximum revenue profit. We also have the price table, which tells us the worth of the rod.

Length =	1	2	3	4	5
Price =	1	5	6	9	10

So, according to the above table, if we cut the rod of length 1 we can sell it for $1.

Similarly, if we cut the rod at length 2, we can sell it at $5 and if we cut the rod at length 3, we can sell it at $6.

According to the problem, we need to find a way, how to cut the rod so that we can get maximum profit.

Here rod length is 5, so if we give the whole rod, without cutting it so the profit is $10. But if we cut the rod at length 2 and at length 3 (so total rod size is 2+3 = 5), then the total profit will be 5 + 6 = 11. This gives us maximum profit.

Dynamic programming solution

static void Main(string[] args) {
    int[] price = new int[] {
        1,
        5,
        6,
        9,
        10
    };
    int length = price.Length;
    Console.WriteLine("Total Profit is :- " + Class1.TotalProfitToCutRod(price, length));
}
public static int TotalProfitToCutRod(int[] p, int n) {
    int[] r = new int[n + 1];
    r[0] = 0;
    for (int j = 1; j <= n; j++) {
        int q = int.MinValue;
        for (int i = 1; i <= j; i++) {
            q = Math.Max(q, p[i - 1] + r[j - i]);
        }
        r[j] = q;
    }
    return r[n];
}

C#

In this implementation, p is the array of prices for each piece length of rod and n is the length of the rod. This function returns the maximum profit that we get by cutting up the rod.

Naive recursive solution

static void Main(string[] args) {
    int[] price = new int[] {
        1,
        5,
        6,
        9,
        10
    };
    int length = price.Length;
    Console.WriteLine("Total Profit is :- " + Class1.TotalProfitToCutRod(price, length));
}
public static int TotalProfitToCutRod(int[] p, int n) {
    if (n <= 0) return 0;
    int maximum_val = int.MinValue;
    for (int i = 0; i < n; i++) maximum_val = Math.Max(maximum_val, p[i] + TotalProfitToCutRod(p, n - i - 1));
    return maximum_val;
}

C#

 

----------------------------------------------------------------