দুটি ভিন্ন অ্যারে leftDis এবং rightDis তৈরি করুন। leftDis বাম দিক থেকে যাওয়ার সময় মান স্টোর করবে। rightDis ডান দিক থেকে যাওয়ার শর্টেস্ট মান স্টোর করবে। যখনই ক্যারেক্টার মেলে, ক্যারেক্টারের পজিশন অ্যারেতে যোগ করুন। শেষ ধাপে দুটি অ্যারের ম্যাক্সিমাম ক্যালকুলেট করুন।
টাইম কমপ্লেক্সিটি − O(n)
স্পেস কমপ্লেক্সিটি − O(n)
উদাহরণ
public class Arrays{ public int[] LongestDistanceToCharacter(string s, char c){ int stringLength = s.Length; int[] leftDis = new int[s.Length]; int[] rightDis = new int[s.Length]; leftDis = Enumerable.Range(0, s.Length).Select(n => int.MinValue).ToArray(); rightDis = Enumerable.Range(0, s.Length).Select(n => int.MaxValue).ToArray(); int count = int.MaxValue; for (int i = 0; i < rightDis.Length; i++){ if (s[i] == c){ count = 0; rightDis[i] = count; } else{ if (count != int.MaxValue){ count++; rightDis[i] = count; } } } count = int.MaxValue; for (int i = leftDis.Length - 1; i >= 0; i--){ if (s[i] == c){ count = 0; leftDis[i] = count; } else{ if (count != int.MaxValue){ count++; leftDis[i] = count; } } } int[] ans = new int[stringLength]; for (int i = 0; i < stringLength - 1; i++){ ans[i] = Math.Max(leftDis[i], rightDis[i]); } return ans; } } static void Main(string[] args){ Arrays s = new Arrays(); string ss = "lovecode"; char c = 'e'; var res = s.LongestDistanceToCharacter(ss, c); foreach (var item in res){ Console.WriteLine(item); } }আউটপুট
[2147483647,2147483647,2147483647,0,3,2,3,0]
